🚦 최단 경로 알고리즘 완전 정리

(Dijkstra / Bellman-Ford / Floyd-Warshall)

---

✅ 최단 경로란?

그래프에서 어떤 정점에서 다른 정점까지 이동할 때의 최소 비용 경로를 의미한다.
이때 간선에 가중치(비용)가 있을 수 있고,
음수 간선이나 모든 정점 쌍의 거리를 요구하는 경우도 있다.

→ 따라서 입력 조건에 따라 다른 알고리즘을 선택해야 한다.

---

✅ 알고리즘 종류 및 비교 요약

알고리즘	시작점	가중치 조건	음수 사이클 감지	시간복잡도
Dijkstra	단일 출발	양수만 허용	❌ 불가능	O((V + E) log V)
Bellman-Ford	단일 출발	음수 O	✅ 가능	O(VE)
Floyd-Warshall	모든 정점 쌍	음수 O	✅ 가능 (dist[i][i] < 0)	O(V³)

---

🟩 Dijkstra 다익스트라

🔸 개념

• 출발 정점에서 시작하여, 가장 가까운 노드부터 확장
• 항상 최단 거리 노드만 선택해서 탐색
• 음수 간선이 있으면 절대 사용하면 안 됨

🔸 구현 (우선순위 큐 기반)

import heapq

def dijkstra(graph, start):
    n = len(graph)
    distance = [float('inf')] * n
    distance[start] = 0
    pq = [(0, start)]  # (비용, 노드)

    while pq:
        dist, now = heapq.heappop(pq)
        if dist > distance[now]:
            continue
        for neighbor, cost in graph[now]:
            new_dist = dist + cost
            if new_dist < distance[neighbor]:
                distance[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distance

# 예시
graph = {
    0: [(1, 2), (2, 5)],
    1: [(2, 1), (3, 2)],
    2: [(3, 3)],
    3: []
}
print("최단 거리:", dijkstra(graph, 0))  # [0, 2, 3, 4]

---

🟨 Bellman-Ford

🔸 개념

• 모든 간선을 V - 1번 반복해서 확인
• 음수 간선이 포함되어도 안전하게 동작
• 마지막에 음수 사이클 존재 여부도 확인 가능

🔸 구현

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

    for i in range(n - 1):
        for u, v, cost in edges:
            if distance[u] != float('inf') and distance[u] + cost < distance[v]:
                distance[v] = distance[u] + cost

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

    return distance

# 예시
edges = [(0, 1, 2), (1, 2, -3), (2, 3, 2), (3, 1, 1)]
print("최단 거리:", bellman_ford(4, edges, 0))  # None (음수 사이클)

---

🟦 Floyd-Warshall

🔸 개념

• 모든 정점 쌍 간의 최단 거리 구하기
• 2차원 DP 테이블 기반
  → dist[i][j] = i에서 j까지의 최단 거리

🔸 구현

def floyd_warshall(n, graph):
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0
    for u, v, cost in graph:
        dist[u][v] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 예시
graph = [
    (0, 1, 4),
    (0, 2, 1),
    (2, 1, 2),
    (1, 3, 1),
    (2, 3, 5)
]
dist = floyd_warshall(4, graph)
for row in dist:
    print(row)

🔸 음수 사이클 감지

def has_negative_cycle(dist):
    for i in range(len(dist)):
        if dist[i][i] < 0:
            return True
    return False

---

✅ 최단 경로 알고리즘 비교 (최종 정리표)

알고리즘	목적	입력 구조	시간복잡도	음수 가중치	음수 사이클 감지	사용 상황	속도 체감
Dijkstra	한 정점 → 모든 정점	인접 리스트 + 우선순위 큐	O((V + E) log V)	❌ 안 됨	❌ 불가	지도, 경로 탐색	빠름
Bellman-Ford	한 정점 → 모든 정점	간선 리스트	O(VE)	✅ 가능	✅ 가능	환율 계산, 음수 간선	느림
Floyd-Warshall	모든 정점 쌍	인접 행렬 (2차원 DP)	O(V³)	✅ 가능	✅ 가능 (dist[i][i] < 0)	전체 거리 미리 계산	매우 느림

---

✅ 언제 어떤 알고리즘을 쓰면 될까?

상황	추천 알고리즘
양수 가중치, 빠른 단일 출발	Dijkstra
음수 간선 존재	Bellman-Ford
모든 정점 쌍 거리 필요	Floyd-Warshall
음수 사이클 판별 필요	Bellman-Ford, Floyd-Warshall

---

🎯 마무리 요약

• 최단 경로 알고리즘은 입력 조건(음수, 출발점 수, 전체 쌍 여부 등)에 따라 선택이 달라져야 한다.
• Dijkstra는 가장 빠르지만 음수 간선에서는 절대 사용하면 안 된다.
• Bellman-Ford는 음수 간선과 사이클까지 커버할 수 있는 유일한 단일 출발 알고리즘이다.
• Floyd-Warshall은 모든 정점 쌍 간의 거리 계산에 탁월하지만, 느리기 때문에 V가 작을 때 사용한다.
• 단, 모든 간선의 가중치가 1일 때는 BFS가 최단 거리 탐색에 최적화 되는 걸 기억하자.