최단 경로 알고리즘 고르기

최단 경로 문제의 갈래

최단 경로(shortest path)는 간선 가중치의 합이 가장 작은 경로다. 알고리즘은 문제의 네 가지 조건으로 갈린다.

가중치가 없는가(모두 같은가), 0과 1뿐인가, 음이 아닌가, 음수도 있는가
음수 사이클이 있을 수 있는가
출발점 하나에서 모든 정점까지(단일 출발점)인가, 모든 정점 쌍(전체 쌍)인가
목적지가 하나로 정해져 있고 목적지까지의 거리를 어림할 수 있는가

무엇을 고르나

조건	알고리즘	시간	핵심
가중치 없음	BFS	O(V + E)	큐에서 먼저 꺼낸 정점이 가장 가깝다
가중치가 0 또는 1	0-1 BFS	O(V + E)	덱을 써서 0 간선은 앞에, 1 간선은 뒤에 넣는다
음수 없음, 단일 출발점	다익스트라	힙 O(E log V), 배열 O(V²)	가장 가까운 미확정 정점을 확정하는 그리디
음수 간선 있음, 단일 출발점	벨만-포드	O(VE)	모든 간선 완화를 V-1번 반복. 음수 사이클을 찾아낸다
DAG(사이클 없음), 음수 가능	위상 순서 완화	O(V + E)	위상 정렬 순서로 한 번씩만 완화하면 된다
전체 쌍, V가 수백 이하	플로이드-워셜	O(V³)	거쳐 갈 정점을 하나씩 늘리는 DP. 음수 간선 가능
전체 쌍, 희소 그래프, 음수 간선	존슨(Johnson)	O(VE log V)	벨만-포드로 가중치를 음이 아니게 바꾼 뒤 다익스트라를 V번
목적지 하나, 거리를 어림하는 함수가 있음	A*	최악은 다익스트라와 같다	「지금까지 거리 + 남은 거리 추정」이 작은 정점부터
트리	DFS·BFS 한 번	O(V)	두 정점 사이 경로가 하나뿐이다

모든 알고리즘의 기본 동작은 완화(relaxation) 다. 간선 u→v(가중치 w)에 대해 dist[u] + w < dist[v]이면 dist[v]를 줄인다. 알고리즘의 차이는 완화를 어떤 순서로, 몇 번 하느냐다.

벨만-포드: 음수 간선

다익스트라는 한번 확정한 정점이 다시 줄지 않는다는 가정에 기대는데, 음수 간선이 있으면 나중에 돌아오는 경로가 더 짧을 수 있어 이 가정이 깨진다. 벨만-포드(Bellman-Ford)는 확정을 포기하고 모든 간선을 V-1번 완화한다.

음수 사이클이 없다면 최단 경로는 같은 정점을 두 번 지나지 않으므로 간선이 많아야 V-1개다. i번째 반복이 끝나면 간선 i개 이하로 가는 최단 거리가 모두 맞아 있으므로 V-1번이면 충분하다.
V번째 반복에서도 줄어드는 거리가 있으면 출발점에서 닿는 음수 사이클이 있다. 그 사이클을 돌 때마다 거리가 줄어 최단 거리가 정의되지 않는다(-∞).

def bellman_ford(n, edges, start):          # edges: (u, v, w)
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:                      # 더 줄지 않으면 일찍 끝낸다
            break
    for u, v, w in edges:                    # 한 번 더 줄면 음수 사이클
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None
    return dist

dist[u] != INF 확인을 빼면 닿지 않는 정점끼리의 음수 간선 때문에 무한대가 줄어드는 잘못된 갱신이 생긴다. 거리가 바뀐 정점의 이웃만 큐로 다시 보는 변형이 SPFA로, 평균은 빠르지만 최악은 O(VE) 그대로다.

플로이드-워셜: 모든 쌍

플로이드-워셜(Floyd-Warshall)은 「1~k번 정점만 거쳐 갈 수 있을 때 i에서 j까지 최단 거리」를 k를 늘려 가며 구하는 동적 계획법이다.

d[i][j] = min(d[i][j], d[i][k] + d[k][j])    k = 1, 2, …, V 순서로

def floyd_warshall(d):                       # d: V×V 인접 행렬, 간선 없으면 INF, d[i][i] = 0
    n = len(d)
    for k in range(n):                       # 거쳐 갈 정점이 가장 바깥 반복이어야 한다
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

시간 O(V³), 공간 O(V²). V가 500이면 1억 2500만 번이라 코딩 테스트에서는 V가 수백 이하일 때 쓴다.
k를 안쪽 반복에 두면 아직 갱신되지 않은 값을 써서 틀린다. 점화식의 단계가 k이기 때문이다.
음수 간선이 있어도 되고, 끝난 뒤 d[i][i] < 0인 i가 있으면 음수 사이클이 있다.

음수 간선과 음수 사이클

상황	쓸 수 있는 것	쓸 수 없는 것
음수 간선, 음수 사이클 없음	벨만-포드(SPFA), 플로이드-워셜, DAG면 위상 순서 완화, 전체 쌍이면 존슨	다익스트라. 이미 확정한 거리가 나중에 줄 수 있다
음수 사이클 있음	벨만-포드·플로이드-워셜로 존재를 판정한다. 사이클에서 닿는 정점의 거리는 -∞로 표시한다	최단 거리 자체가 정의되지 않는다. 「같은 정점을 두 번 지나지 않는 경로」로 바꾸면 NP-난해 문제가 된다

무방향 그래프의 음수 간선은 그 자체로 음수 사이클이다. 양쪽으로 오가면 계속 줄어든다.

A*: 목적지가 하나일 때

A*(에이 스타)는 다익스트라가 힙에서 g(n)(출발점에서 n까지의 거리)이 가장 작은 정점을 꺼내는 대신, f(n) = g(n) + h(n) 이 가장 작은 정점을 꺼낸다. h(n)은 n에서 목적지까지 남은 거리의 추정치(휴리스틱)다. 목적지 방향의 정점을 먼저 보게 되어 다익스트라처럼 사방으로 퍼지지 않는다.

휴리스틱 성질	조건	결과
허용 가능(admissible)	`h(n)`이 실제 남은 거리를 넘지 않는다	찾은 경로가 최단임이 보장된다
일관(consistent)	모든 간선 u→v에서 `h(u) ≤ w(u, v) + h(v)`	정점을 한 번 꺼내면 다시 열 필요가 없다. 다익스트라처럼 동작한다
`h = 0`	-	다익스트라와 같다
실제보다 큰 추정	허용 불가	더 빨리 끝나지만 최단을 놓칠 수 있다

격자 지도에서는 상하좌우 이동이면 맨해튼 거리 |dx| + |dy|, 대각선까지 같은 비용이면 체비쇼프 거리 max(|dx|, |dy|), 아무 방향이나 갈 수 있으면 유클리드 거리를 쓴다.

다익스트라와 비교한 성능은 휴리스틱의 질에 달렸다. 실제 거리에 가까울수록 꺼내는 정점 수가 줄어 목적지 하나를 찾는 데는 크게 빠르다. 휴리스틱이 쓸모없으면(h = 0) 다익스트라와 같고, 최악의 시간 복잡도도 다익스트라와 같다. 다만 출발점에서 모든 정점까지의 거리가 필요하면 A*의 이점이 없다. 열린 정점을 모두 힙에 들고 있어 메모리를 많이 쓴다는 것이 약점이다. 게임의 길 찾기, 로봇 경로 계획, 퍼즐 상태 공간 탐색에 쓴다.

트리에서의 최단 거리

트리는 두 정점 사이 경로가 정확히 하나라 「가장 짧은 경로」를 고를 일이 없다. 출발점에서 DFS나 BFS를 한 번 돌며 dist[child] = dist[parent] + w로 누적하면 모든 정점까지의 거리가 O(V)에 나온다. 가중치가 음수여도 같다. 다익스트라의 힙이 필요 없다.

여러 쌍의 거리를 물으면 루트에서 각 정점까지의 거리 root_dist를 한 번 구해 두고, dist(u, v) = root_dist[u] + root_dist[v] - 2 × root_dist[LCA(u, v)]로 답한다(최소 공통 조상). 트리의 지름(가장 먼 두 정점)은 아무 정점에서 가장 먼 정점 a를 찾고, a에서 다시 가장 먼 정점까지의 거리로 구한다(음이 아닌 가중치일 때).

밀집 그래프: 간선이 V²에 가깝거나 더 많을 때

정점 N개, 간선 N³개처럼 간선이 많으면 복잡도의 E 항이 지배한다.

알고리즘	E = N³을 그대로 넣으면	중복 간선을 접어 E ≤ N² 이면
다익스트라(이진 힙)	O(N³ log N)	O(N² log N)
다익스트라(배열, 인접 행렬)	O(N²)	O(N²)
벨만-포드	O(N⁴)	O(N³)
플로이드-워셜(전체 쌍)	O(N³)	O(N³)

단일 출발점이면 인접 행렬 + 배열 다익스트라 O(V²)가 가장 낫다. 간선을 하나씩 보지 않고 정점마다 행렬의 한 행을 훑기 때문에 간선 수와 무관하다. 단순 그래프는 간선이 V²을 넘을 수 없으므로 간선이 N³개라면 중복 간선이고, 입력을 읽으며 쌍마다 최솟값만 남긴다(그래프의 기본과 표현 방법). 전체 쌍이 필요하면 플로이드-워셜 O(N³)이 다익스트라를 N번 돌리는 O(N³)과 같으면서 구현이 짧다.

정리

최단 경로 알고리즘은 가중치 종류, 음수 사이클, 단일 출발점·전체 쌍, 목적지 하나 여부로 고른다.
모든 알고리즘은 완화의 순서와 횟수만 다르다. 다익스트라는 가까운 순서로 한 번, 벨만-포드는 전체를 V-1번, DAG는 위상 순서로 한 번.
음수 간선이면 벨만-포드나 플로이드-워셜. 둘 다 음수 사이클을 판정한다(V번째 완화가 일어남, d[i][i] < 0).
A*는 허용 가능한 휴리스틱으로 목적지 쪽부터 탐색해 같은 최단 경로를 더 적은 탐색으로 찾는다.
트리는 경로가 하나라 DFS 한 번이면 되고, 밀집 그래프의 단일 출발점은 O(V²) 다익스트라가 낫다.

버그 제보