0x09. 최단 경로 알고리즘

최단 경로 문제란?

내비게이션 앱에서 "최단 경로 안내"를 누르면, 수많은 교차로와 도로 중에서 가장 빠른 길을 찾아준다. 최단 경로(Shortest Path) 알고리즘이 바로 이 문제를 해결한다. (구현 문제 풀이는 다익스트라, 플로이드-워셜 참고)

입력은 방향 그래프(Directed Graph) G = (V, E)와 가중치 함수(Weight Function) w : E → R이다. 출발지에서 목적지까지 가중치 합이 최소인 경로 p를 찾는 것이 목표다.

• 경로의 가중치 w(p): 경로에 포함된 간선 가중치의 합
• 최단 경로 가중치 $\delta$(u, v): u에서 v까지의 최단 경로 가중치

문제의 변형

최단 경로 문제는 네 가지 변형이 존재한다.

• 단일 출발점(Single-source) 최단 경로: 출발점 s $\in$ V에서 모든 정점 v $\in$ V로의 최단 경로를 구한다
• 단일 도착점(Single-destination) 최단 경로: 특정 도착점까지의 최단 경로를 구한다. 그래프의 간선 방향을 뒤집으면 단일 출발점 문제로 환원된다
• 단일 쌍(Single-pair) 최단 경로: 특정 u에서 v까지의 최단 경로를 구한다. 단일 출발점 문제보다 빠르게 풀 수 있는 알고리즘은 알려져 있지 않다
• 모든 쌍(All-pairs) 최단 경로: 모든 정점 쌍 u, v $\in$ V에 대해 최단 경로를 구한다

이 글에서 다루는 알고리즘은 다음과 같다.

최단 경로의 성질

Lemma 24.1 (최적 부분 구조)

최단 경로는 최적 부분 구조(Optimal Substructure) 를 가진다. 즉, 최단 경로의 부분 경로도 최단 경로다.

증명: 어떤 부분 경로가 최단이 아니라고 가정하면, 더 짧은 부분 경로가 존재해야 한다. 그 부분 경로를 대체하면 전체 경로가 더 짧아지므로, 원래 경로가 최단이라는 가정에 모순이 된다.

삼각 부등식(Triangle Inequality)

$\delta$(u, v)를 u에서 v까지의 최단 경로 가중치라 정의하면, 다음이 성립한다.

$\delta(u, v) \le \delta(u, x) + \delta(x, v)$

음수 가중치 간선

음수 가중치 간선 자체는 문제가 되지 않는다. 다만 출발점에서 도달 가능한 음수 가중치 사이클(Negative-weight Cycle) 이 있으면 문제가 된다. 해당 사이클을 무한히 돌 수 있으므로 사이클 내 모든 정점 v에 대해 w(s, v) = $-\infin$이 되어버린다.

일부 알고리즘(예: Dijkstra)은 음수 가중치 간선이 아예 없어야 정상 동작한다.

사이클과 최단 경로

최단 경로에는 사이클이 포함될 수 없다.

• 음수 가중치 사이클: 위에서 설명한 대로 존재하지 않는다고 가정한다
• 양수 가중치 사이클: 사이클을 제거하면 더 짧은 경로를 얻으므로 포함될 이유가 없다
• 0 가중치 사이클: 사용할 이유가 없으므로, 해를 구할 때 사용하지 않는다고 가정한다

단일 출발점 최단 경로 (Single Source Shortest Path)

출발점 s $\in$ V에서 모든 정점 v $\in$ V로의 최단 경로를 구하는 문제다. 각 정점 v $\in$ V에 대해 두 가지 값을 관리한다.

• d[v]: s에서 v까지의 최단 경로 추정값(Shortest-path Estimate)
  • 초기에는 d[v] = $\infin$으로 설정한다
  • 알고리즘이 진행되면서 d[v]를 줄여나가되, 항상 d[v] $\ge$ $\delta$(s, v)를 유지한다
• $\pi$[v]: 최단 경로 트리에서 v의 선행자(Predecessor)
  • 선행자가 없으면 $\pi$[v] = NIL이다
  • $\pi$가 유도하는 트리가 최단 경로 트리(Shortest-path Tree) 다

초기화 (Initialization)

완화 (Relaxation)

최단 경로 알고리즘의 핵심 기법은 완화(Relaxation) 다. 모든 정점 v에 대해 d[v]를 $\delta$(s, v)의 상한(Upper Bound) 으로 유지하면서, 더 짧은 경로를 발견할 때마다 값을 갱신한다.

간선 (u, v)에 대해 u를 거쳐 v로 가는 경로가 기존 d[v]보다 짧으면, d[v]와 $\pi$[v]를 갱신하는 것이 완화 연산이다.

Bellman-Ford 알고리즘

Bellman-Ford 알고리즘은 간선 가중치가 음수인 경우에도 동작하는 단일 출발점 최단 경로 알고리즘이다. 출발점에서 도달 가능한 음수 가중치 사이클이 없는 한 올바른 결과를 보장한다.

반환값은 boolean이다.

• 음수 가중치 사이클이 존재하면 FALSE
• 존재하지 않으면 TRUE (정상적으로 최단 경로를 구한 경우)

의사 코드

첫 번째 루프에서 모든 간선을 |V| - 1번 완화한다.

시간 복잡도: $\Theta$(VE)

실행 예시

음수 가중치 사이클 예시

음수 가중치 사이클이 있으면 d 값이 계속 줄어들기만 하고, 최단 경로가 수렴하지 않는다.

DAG 최단 경로

DAG(Directed Acyclic Graph) 에서의 최단 경로는 Bellman-Ford의 $\Theta$(VE)보다 더 빠르게 구할 수 있다. 핵심 아이디어는 위상 정렬(Topological Sort) 을 활용하는 것이다.

DAG에는 사이클이 없으므로, 모든 경로는 위상 정렬 순서의 부분 수열이다. 위상 정렬 순서대로 정점을 왼쪽에서 오른쪽으로 처리하면, 한 번의 순회만으로 최단 경로를 구할 수 있다.

실행 예시

의사 코드

시간 복잡도: $\Theta$(V+E)

Dijkstra 알고리즘

음수 가중치 간선이 없다면, Bellman-Ford보다 더 빠른 알고리즘을 사용할 수 있다. 그것이 바로 Dijkstra 알고리즘이다.

Dijkstra는 BFS(너비 우선 탐색)의 가중치 버전이라고 생각하면 이해하기 쉽다. BFS가 FIFO 큐를 사용하는 것과 달리, Dijkstra는 우선순위 큐(Priority Queue) 를 사용하며 키는 최단 경로 추정값 d[v] 다. 트리를 서서히 확장하면서 큐에서 꺼낸 정점을 처리한다.

알고리즘은 두 개의 정점 집합을 관리한다.

• S: 최단 경로가 확정된 정점의 집합
• Q: 우선순위 큐 = V - S (아직 확정되지 않은 정점)

동작 방식은 다음과 같다.

1. 그래프 G = (V, E)에 대해, 최단 경로가 확정된 정점의 집합 S를 유지한다
2. Q에서 최소 d[v] 값을 가진 정점 u를 반복적으로 선택하여 S에 추가한다
3. u에서 나가는 모든 간선을 완화한다

이 전략은 탐욕법(Greedy) 에 해당한다.

의사 코드

실행 예시: s에서 t까지의 최단 경로

정확성 (Correctness)

Theorem 24.6: while 루프(4-8행)의 각 반복이 시작될 때, S에 속한 모든 정점 v에 대해 d[v] = $\delta$(s, v)가 성립한다는 루프 불변식(Loop Invariant) 이 보장된다.

음수 가중치 간선에서의 실패

큐가 비어서 알고리즘이 종료되었지만, 경로 A → C → B → D의 총 길이는 5 + (-4) + 1 = 2로 기존에 계산된 4보다 짧다. 즉, 출발점 A에서 D까지의 최단 경로가 올바르게 계산되지 않았다. Dijkstra 알고리즘은 음수 가중치 간선이 있으면 정상 동작하지 않는다.

시간 복잡도 분석

Prim 알고리즘과 마찬가지로, 성능은 우선순위 큐의 구현 방식에 따라 달라진다.

모든 쌍 최단 경로 (All Pairs Shortest Path)

단순한 접근법

모든 쌍 최단 경로를 구하는 가장 단순한 방법은 Dijkstra나 Bellman-Ford를 |V|번 반복하는 것이다.

밀집 그래프(Dense Graph)에서 E = O(V$^2$)일 때, Dijkstra를 반복하면 O(V$^3$ lg V), Bellman-Ford를 반복하면 O(V$^4$)가 된다. 더 빠른 알고리즘은 없을까?

Floyd-Warshall 알고리즘

Floyd-Warshall 알고리즘은 모든 쌍 최단 경로를 효율적으로 구하는 동적 프로그래밍(Dynamic Programming) 기반 알고리즘이다.

• 음수 가중치 간선을 허용한다
• 단, 음수 가중치 사이클은 없다고 가정한다
• 최적 부분 구조(Optimal Substructure) 를 활용한다

최단 경로의 구조: 중간 정점

중간 정점(Intermediate Vertex) 이란, 단순 경로 p = (v$_1$, ..., v$_L$)에서 시작점 v$_1$과 끝점 v$_L$을 제외한 나머지 정점, 즉 {v$_2$, ..., v$_{L-1}$}에 속하는 정점을 말한다.

핵심 관찰:

임의의 정점 쌍 i, j에 대해, 중간 정점이 모두 {1, 2, ..., k}에 속하는 최소 가중치 경로를 p라 하자. 이때 {1, 2, ..., k-1}만을 중간 정점으로 사용하는 최단 경로는 이미 구해져 있다고 가정한다(부분 문제). 경로 p와 이 부분 문제의 관계를 살펴보면 Floyd-Warshall의 점화식을 유도할 수 있다.

핵심 관찰: 두 가지 경우

먼저, 최단 경로에는 동일한 정점이 두 번 등장하지 않는다. 같은 정점이 두 번 나타나면 사이클이 존재하는 것이고, 사이클을 제거하면 더 짧은 경로를 얻을 수 있기 때문이다.

경로 p는 중간 정점이 {1, ..., k-1}인 최단 경로들로 결정된다.

• Case 1: k가 경로 p의 중간 정점이 아닌 경우
  • p는 중간 정점이 {1, ..., k-1}인 i에서 j까지의 최단 경로와 동일하다
• Case 2: k가 경로 p의 중간 정점인 경우
  • p를 i → p1 → k → p2 → j로 분해할 수 있다
  • p1은 중간 정점이 {1, 2, ..., k-1}인 i에서 k까지의 최단 경로
  • p2는 중간 정점이 {1, 2, ..., k-1}인 k에서 j까지의 최단 경로

재귀적 해 (Recursive Solution)

$d_{ij}^{(k)}$를 중간 정점이 모두 {1, 2, ..., k}에 속하는 조건에서 i에서 j까지의 최단 경로 길이라 하자.

예를 들어, $d_{13}^{(4)}$는 중간 정점으로 1, 2, 3, 4만 사용하여 정점 1에서 정점 3까지 가는 최단 경로다.

D(k)를 $d_{ij}^{(k)}$로 구성된 n x n 행렬이라 하면, 점화식은 다음과 같다.

• 기저: $d_{ij}^{(0)}$ = $w_{ij}$ (중간 정점 없이 직접 연결)
• 점화식 (k $\ge$ 1):

$d_{ij}^{(k)} = \min(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)})$

k를 중간 정점으로 사용하지 않는 경우와 사용하는 경우 중 더 작은 값을 택한다.

최종 답은 D(n) = ($d_{ij}^{(n)}$)이다. 모든 중간 정점이 {1, 2, ..., n}에 속하므로 $d_{ij}^{(n)}$ = $\delta$(i, j)가 모든 i, j $\in$ V에 대해 성립한다.

최단 경로 추출 (Extracting the Shortest Paths)

실제 경로를 복원하려면 선행자 포인터 pred[i, j] 를 활용한다.

초기화:

• pred[i, j] = NIL (i = j이거나 $w_{ij}$ = $\infin$인 경우)
• pred[i, j] = i (i $\ne$ j이고 $w_{ij}$ < $\infin$인 경우)

알고리즘 진행 중 i에서 j까지 중간 정점 k를 경유하는 더 짧은 경로가 발견되면, pred[i, j] = k로 갱신한다.

관찰:

• pred[i, j] = NIL이면 최단 경로가 존재하지 않는다
• 최단 경로가 존재하면서 중간 정점을 거치지 않으면 pred[i, j] = i이다
• pred[i, j] = k이면, 정점 k가 i에서 j까지의 최단 경로상 중간 정점이다

경로 복원 방법:

• pred[i, j] = i이면 최단 경로는 간선 (i, j) 자체다
• 그렇지 않으면 (i, pred[i, j])와 (pred[i, j], j)를 재귀적으로 계산한다

Bottom-up 방식으로 가중치 계산

실행 예시

연습 문제

복잡도 분석

Floyd-Warshall의 시간 복잡도는 $\Theta$(|V|$^3$) 이다.

단일 출발점 알고리즘을 |V|번 반복하는 방식과 비교하면 다음과 같다.

Floyd-Warshall이 기존 방식보다 빠르다. 다만 공간 복잡도가 $\Theta$(|V|$^3$) 라는 점이 문제인데, 행렬을 n개 유지하는 대신 하나의 행렬만 유지하면 $\Theta$(|V|$^2$)로 줄일 수 있다.

개선된 버전

이행적 폐쇄 (Transitive Closure)

방향 그래프 G = (V, E)가 주어졌을 때, 이행적 폐쇄 G$^*$ = (V, E$^*$)를 구하는 문제다. 여기서 E$^*$ = {(i, j) : G에서 i에서 j로의 경로가 존재}이다.

Floyd-Warshall을 활용하면 간단하게 구할 수 있다.

1. 모든 간선의 가중치를 1로 설정하고 Floyd-Warshall을 실행한다
2. $d_{ij}$ < n이면 i에서 j로의 경로가 존재
3. $d_{ij}$ = $\infin$이면 경로가 존재하지 않는다

더 효율적인 방법으로는 논리 연산 OR, AND를 사용하는 방식이 있다. 가중치 1을 할당한 뒤, Floyd-Warshall의 min과 +를 각각 OR과 AND로 대체하여 실행한다.

연습 문제 (Exercise)

1. Dijkstra 알고리즘

정점 D가 우선순위 큐에서 추출되고, D에서 나가는 모든 간선이 완화된 후 B, C, E의 거리는?

B = 3(A), C = 8(B), E = 10(D)

2. Floyd 알고리즘

DP를 활용한 풀이:

3. 모든 쌍 최단 경로: Floyd를 쓰는 이유

단일 출발점 알고리즘을 반복하여 모든 쌍 최단 경로를 구할 수도 있다.

• Dijkstra x V: $\Theta$(V$^3$)
• Bellman-Ford x V: $\Theta$(V$^4$)
• Floyd-Warshall: $\Theta$(V$^3$)

시간 복잡도만 보면 Dijkstra를 V번 반복하는 것과 Floyd-Warshall이 비슷해 보인다. 그런데 왜 Floyd-Warshall을 사용하는가? Floyd-Warshall은 음수 가중치 간선을 처리할 수 있기 때문이다. Dijkstra는 음수 가중치 간선이 있으면 정상 동작하지 않는다.

HGU 전산전자공학부 용환기 교수님의 23-1 알고리듬 분석 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.