최단 경로 알고리즘 완전 정복: 다익스트라, 벨만포드, 플로이드 워셜 차이와 구현

최단 경로 알고리즘 완전 정복: 다익스트라, 벨만포드, 플로이드 워셜 차이와 구현

그래프에서 두 정점 사이의 **최단 경로(Shortest Path)**를 찾는 문제는 알고리즘에서 가장 중요한 주제 중 하나입니다.
이 글에서는 세 가지 대표적인 최단 경로 알고리즘인
다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), **플로이드 워셜(Floyd-Warshall)**을
원리, 적용 조건, 구현 코드, 시간복잡도 중심으로 비교·정리합니다.

---

🧭 언제 어떤 알고리즘을 써야 할까?

알고리즘 음수 간선 모든 쌍 간선 시간복잡도 특징

다익스트라	❌ (음수X)	❌ (단일 출발)	O(E log V)	양의 가중치만, 가장 빠름
벨만-포드	✅	❌	O(V × E)	음수 가능, 음수 사이클 탐지
플로이드-워셜	✅	✅	O(V³)	모든 노드 쌍 간 최단 경로 구함

---

✅ 1. 다익스트라 알고리즘 (Dijkstra)

하나의 시작점에서 모든 정점까지의 최단 경로
단, 음수 간선이 없어야 함

📌 핵심 아이디어

• 출발점부터 거리가 가장 짧은 노드를 선택
• 인접 노드를 업데이트 (Greedy 방식)
• 우선순위 큐(Heap)을 사용해 속도 개선

🧪 Python 구현 (heapq 사용)

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    queue = [(0, start)]

    while queue:
        cost, node = heapq.heappop(queue)
        if cost > dist[node]:
            continue

        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor))
    
    return dist

graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [('D', 2)],
    'C': [('B', 2), ('D', 4)],
    'D': []
}

print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 3, 'C': 1, 'D': 5}

---

✅ 2. 벨만-포드 알고리즘 (Bellman-Ford)

음수 간선 허용, 단 음수 사이클이 있으면 사용 불가
한 정점에서 모든 노드로의 최단 경로를 계산

📌 핵심 아이디어

• 모든 간선을 V-1번 반복하며 업데이트
• 이후 1번 더 반복해서 음수 사이클 검출

🧪 Python 구현

반응형

def bellman_ford(edges, V, start):
    dist = [float('inf')] * V
    dist[start] = 0

    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 음수 사이클 체크
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return "음수 사이클 존재"

    return dist

edges = [
    (0, 1, 4),
    (0, 2, 5),
    (1, 2, -3),
    (2, 3, 4)
]

print(bellman_ford(edges, 4, 0))  # [0, 4, 1, 5]

---

✅ 3. 플로이드-워셜 알고리즘 (Floyd-Warshall)

모든 정점 쌍 사이의 최단 경로를 구할 때 사용
음수 간선 가능, 단 음수 사이클은 없어야 함

📌 핵심 아이디어

• 점화식:
  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

🧪 Python 구현

def floyd_warshall(graph):
    n = len(graph)
    dist = [row[:] for row in graph]  # 복사

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

INF = float('inf')
graph = [
    [0,     3,     INF,   7],
    [8,     0,     2,     INF],
    [5,     INF,   0,     1],
    [2,     INF,   INF,   0]
]

result = floyd_warshall(graph)
for row in result:
    print(row)

---

⚠️ 실전 사용 팁

상황 추천 알고리즘

단일 출발점, 양의 가중치	✅ 다익스트라
단일 출발점, 음의 간선 가능	✅ 벨만-포드
모든 정점 간 최단 거리	✅ 플로이드-워셜
간선 개수 많고 음수 사이클 확인 필요	✅ 벨만-포드
희소 그래프 (간선 적고 정점 많음)	✅ 다익스트라 + heap

---

📌 결론 및 요약

• 다익스트라: 가장 빠르고 자주 쓰이는 최단 경로 알고리즘 (단, 음수 간선 불가)
• 벨만-포드: 음수 간선/사이클이 있는지 확인할 때 유용
• 플로이드-워셜: 모든 정점 쌍 간 최단 경로 구할 때 간단하고 강력

👉 다음 글에서는 **최소 신장 트리(MST: Minimum Spanning Tree)**에 대해
**크루스칼(Kruskal)**과 프림(Prim) 알고리즘을 비교하며 정리합니다.

---

📚 참고자료 및 출처

• 『이것이 취업을 위한 코딩테스트다 with Python』
• 백준 1753, 1865, 11404
• GeeksforGeeks – Shortest Path Algorithms

---

 

최단경로, 다익스트라, 벨만포드, 플로이드워셜, 그래프 알고리즘, 파이썬 그래프, 코딩테스트 준비, 가중치 그래프, 음수 간선, SEO 최적화 10개