학부 수업 "알고리즘설계와분석" 내용을 정리한다.

최단경로를 구하는 두 가지 핵심 알고리즘인 Bellman-Ford와 Dijkstra의 원리와 차이점에 대해 알아보자.

1️⃣ 최단경로의 기본 개념

1-1 최단경로의 정의

그래프의 각 간선에는 가중치(weight)가 주어진다. 어떤 경로 p의 가중치는 경로에 포함된 모든 간선 가중치의 합이다.

w(p) = ∑_{(u,v) ∈ p} w(u,v)

시작점 u에서 목적지 v까지의 최단경로 가중치 δ(u,v)는 다음과 같이 정의한다.

δ(u,v) = min_{u → v 경로 p} w(p)

경로가 존재하지 않으면 δ(u,v) = +∞이다.

🔥 핵심 사실

• δ(s, v)는 s→v까지의 shortest distance를 의미한다
• 최단경로는 unique할 필요 없다 (여러 개 존재 가능)
• 최단경로에는 cycle이 없다 (simple path)

1-2 최단경로의 부분경로 성질

최단경로 p = ⟨v₀, v₁, ..., vₖ⟩가 있을 때, 이 경로의 임의의 부분경로 pᵢⱼ = ⟨vᵢ, ..., vⱼ⟩도 반드시 최단경로이다.

💡 왜 그럴까?

만약 부분경로보다 더 짧은 경로가 존재한다면, 그 경로를 원래 경로 중간에 끼워 넣어 전체 경로를 더 짧게 만들 수 있다. 이는 원래 경로가 최단경로라는 가정에 모순이다.

이 성질은 최단경로 알고리즘의 correctness 증명에서 핵심 개념이다.

1-3 최단경로에 사이클이 없는 이유

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

• 음수 사이클: 최단경로가 정의되지 않음 (무한히 감소)
• 양수 사이클: 제거하면 경로가 더 짧아짐
• 0 사이클: 있어도 되고 없어도 되지만, 제거해도 길이가 같음

따라서 최단경로는 simple path이며, 정점이 n개이면 최대 n-1개의 간선으로 구성된다.

1-4 음수 가중치 사이클

그래프에 negative-weight cycle이 있으면 사이클을 반복하여 가중치가 무한히 감소한다. 따라서 최단경로는 정의될 수 없다.

모든 최단경로 알고리즘은 음수 사이클이 없는 경우에만 의미가 있다.

2️⃣ Relaxation의 개념

2-1 Relaxation이란?

Relax(u, v) 는 다음을 의미한다.

if v.d > u.d + w(u,v) then v.d = u.d + w(u,v)

즉, "u를 거쳐서 v로 가는 경로가 지금까지 알고 있던 것보다 더 짧다면 갱신하라"는 의미다.

🔥 Update Rule

dist[v] = min(dist[v], dist[u] + w(u,v))

2-2 Relaxation의 성질

Relax 후에는 항상 다음이 성립한다.

v.d ≤ u.d + w(u,v)

이는 Relax 과정이 절대 잘못된(과소) 값을 만들지 않는다는 뜻이다.

2-3 Convergence Lemma (수렴 보장)

최단경로가 s → u → v라고 하자. 만약 u.d = δ(s,u)가 이미 맞게 설정되어 있는 상태에서 간선 (u,v)를 relax하면, v.d = δ(s,v)가 된다.

즉, 최단경로의 앞부분이 완성되면 다음 정점도 즉시 최단값으로 수렴한다.

2-4 Path Relaxation Property

최단경로 s = v₀ → v₁ → ⋯ → vₖ의 간선들을 순서대로 relax하면 마지막 vₖ의 값은 반드시 vₖ.d = δ(s,vₖ)를 만족한다.

이 성질 때문에 Bellman-Ford는 모든 간선을 여러 번 반복해서 relax할 필요 없이 |V|-1번만 반복하면 충분하다.

3️⃣ Bellman-Ford 알고리즘

목적

• 음수 edge가 있어도 동작
• 음수 cycle만 없으면 shortest path 존재
• 모든 edge를 총 |V|-1번 relax하면 정답 도달

3-1 알고리즘 구조

Initialize-Single-Source(G, s)

for i = 1 to |V|-1:
    for 모든 간선 (u, v) ∈ E:
        RELAX(u, v)

for 모든 간선 (u, v):
    if v.d > u.d + w(u,v):
        return FALSE   // 음수 사이클 존재

return TRUE            // 최단경로 성공적 계산

🔥 알고리즘 흐름

1. 초기에 모든 정점까지의 거리를 ∞로 설정하고, 출발점 s는 0으로 둔다
2. 모든 간선을 대상으로 d[v] > d[u] + w(u, v)를 만족하면 d[v]를 갱신한다
3. 이 과정을 총 n-1번 반복하면 모든 최단경로가 안정된다
4. 마지막으로 모든 간선을 다시 검사했을 때 유효한 Relaxation이 또 가능하다면 음수 사이클이 존재한다

3-2 정확성 (Correctness)

🔥 왜 정답이 되는가?

1. 최단경로는 simple path이므로 최대 |V|-1개의 간선만 사용
2. Relaxation은 절대 오류값을 만들지 않는다
3. Convergence Lemma + Path Relaxation Property에 의해 최단경로가 반드시 |V|-1번 반복 중에 완성
4. 따라서 알고리즘이 끝나면 v.d = δ(s,v)이 보장된다

3-3 음수 사이클 검출

마지막에 한 번 더 검사했을 때 아직도 v.d > u.d + w(u,v)인 경우가 있다면 음수 사이클이 존재한다.

3-4 시간복잡도

• Relax 단계: 모든 간선을 |V|-1번 검사
• 음수 사이클 검출: 모든 간선을 1번 검사

전체 복잡도: O(VE)

Sparse graph에서는 O(nm), dense graph에서는 O(n³)에 가깝다.

3-5 동작 예시

그래프에 8개의 정점이 있다면 최단경로는 최대 7개의 간선을 포함하므로 Relaxation을 7번 반복한다.

• 초기: 모든 dist 값이 ∞
• 1회 반복 후: 출발점에서 한 간선으로 도달할 수 있는 정점들의 dist 갱신
• 2회 반복 후: dist가 다시 갱신
• 7회 반복 후: 모든 최단경로 결정

음수 간선이 있어도 잘 동작하지만, 음수 사이클이 존재하면 알고리즘은 false로 종료한다.

4️⃣ Dijkstra 알고리즘

목적

• 음수 간선이 없을 때 Bellman-Ford보다 훨씬 빠른 알고리즘
• 매 단계에서 현재까지 dist 값이 가장 작은 정점을 '확정'
• BFS는 Dijkstra의 "모든 간선 가중치가 1인 특수 케이스"

4-1 알고리즘 구조

Initialize-Single-Source(G, s)

모든 정점을 min-heap에 넣는다

while heap이 비어있지 않음:
    u = EXTRACT-MIN(heap)

    for u와 인접한 정점 v:
        if v.d > u.d + w(u,v):
            v.d = u.d + w(u,v)
            DECREASE-KEY(heap, v)

🔥 알고리즘 흐름

1. 모든 dist 값을 ∞로 두고, s.dist = 0
2. 모든 정점을 min-heap에 넣는다
3. heap에서 dist가 가장 작은 정점 u를 꺼내면 → u의 최단거리는 확정된다
4. u와 인접한 정점 v들에 대하여 d[v] > d[u] + w(u,v)이면 갱신하고, heap에서 decrease-key를 수행한다
5. heap이 빌 때까지 반복한다

4-2 Bellman-Ford와의 차이

• Bellman-Ford: 그래프 전체의 모든 간선을 매 반복마다 검사
• Dijkstra: 추출된 정점 u의 인접 간선만 검사

음수 간선이 없다면, u에서 다른 간선을 하나 더 지나면 거리가 늘어나므로 u는 확정할 수 있다.

💡 핵심 아이디어

Dijkstra는 dist가 작은 순서대로 정점을 확정하는데, 이 순서가 곧 **'출발점에서의 거리 증가 순서'**이다.

따라서 Extract-Min되는 순간, 그 정점의 최단거리는 확정된다.

4-3 동작 예시

예시 그래프에서 A를 source라고 하자.

초기 heap

• A는 0
• 다른 정점들은 ∞

Step 1

• heap에서 A가 extract-min
• A와 인접한 B와 C의 거리를 각각 3, 1로 갱신

Step 2

• heap에서 C가 다음으로 가장 작으므로 extract-min
• C의 이웃들에 대해 Relaxation 수행
• B의 거리가 기존 3에서 C(1)+1=2로 갱신

반복

• 각 단계에서 "가장 가까운 정점"을 확정해 나간다

4-4 시간복잡도

• 초기화: O(n)
• Extract-Min: n번, 각 O(log n)
• Decrease-Key: edge마다 최대 한 번, O(E log n)

전체 복잡도: O(E log n)

Bellman-Ford의 O(VE)와 비교하면 훨씬 빠르다.

4-5 음수 간선이 있을 때 실패하는 이유

🔥 문제 상황

1. 어떤 정점 D가 초기에 dist = 1로 확정됨
2. 이후 C에서 D로 음수 간선을 따라가면 D의 거리가 더 줄어들어야 함
3. 하지만 D는 이미 한 번 확정되어 heap에서 제거된 상태 → 더 갱신할 수 없음
4. 따라서 잘못된 최단거리가 출력됨

💡 핵심 문제

"Extract-Min 시점에 그 정점의 최단거리가 확정된다고 가정하는데, 음수 간선이 존재하면 이 가정이 깨진다."

이미 확정한 정점도 나중에 더 짧아질 수 있어 알고리즘 논리가 무너진다.

5️⃣ 알고리즘 비교 및 공통점

5-1 Bellman-Ford vs Dijkstra

5-2 Greedy 확장 패턴의 공통점

Dijkstra, BFS, Prim은 모두 "지금까지 가장 가까운 정점부터 확장한다"는 공통된 틀을 가진다.

🔥 핵심

Dijkstra, BFS, Prim은 모두 Greedy한 확장 패턴을 공유하는 알고리즘이다.