[알고리즘] Bellman-Ford

Bellman–Ford 알고리즘 정리

Bellman–Ford는 단일 시작점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
음수 가중치를 가진 그래프에서도 동작하며, 음수 사이클 감지도 가능하다.
간선 리스트(edge list)를 기반으로 하는 대표적인 relaxation 알고리즘이다.

1. 해결하는 문제

Single Source Shortest Path 문제

음수 가중치 허용

Negative cycle 감지 가능

시간 복잡도는 O(VE)로 다익스트라보다 느리다

2. 핵심 아이디어: Relaxation

각 간선 (u, v, w)에 대해 다음 연산을 반복한다.

if dist[u] + w < dist[v]:
dist[v] = dist[u] + w

이를 통해 “더 짧은 경로를 발견하면 갱신”하는 방식으로 점차 최단 거리가 확정된다.

3. 왜 V - 1번 반복하는가

정점이 V개인 그래프에서 최단 경로는 최대 V - 1개의 간선을 포함한다.
따라서 모든 최단 경로가 고려되도록 간선 relaxation을 V - 1번 반복해야 한다.

즉. 전체 그래프 정보가 모두 반영이 되려면(갱신된 거리 값이 다른 노드로 전파되려면) 여러 루프를 거쳐야 한다.

그래서 V−1번 반복해야 전체 반영이 끝난다.

4. 알고리즘 수행 흐름

dist 배열 초기화

시작 정점 s: dist[s] = 0

나머지 모든 정점: ∞

V - 1번 반복

모든 간선에 대해 relaxation 수행

음수 사이클 검사

한 번 더 모든 간선을 검사

더 갱신되면 음수 사이클 존재해서 루프 반복

5. 예시 그래프

정점: 0, 1, 2, 3
시작 정점: 0

예시 간선 목록:

u, v, w
0, 1, 6
0, 2, 7
1, 2, 8
1, 3, 5
2, 3, -3

초기값:

dist = [0, ∞, ∞, ∞]

1회차 갱신

0 → 1: dist[1] = 6

0 → 2: dist[2] = 7

1 → 3: dist[3] = 11

2 → 3: dist[3] = 4

결과:

dist = [0, 6, 7, 4]

2회차, 3회차

더 이상 변화 없음.

최종 최단 경로:

dist = [0, 6, 7, 4]

6. 의사코드 (Pseudocode)

function BellmanFord(V, edges, source):
    dist = array of size V filled with INF
    dist[source] = 0

for i from 1 to V - 1:
    for each (u, v, w) in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

for each (u, v, w) in edges:
    if dist[u] + w < dist[v]:
        print("Negative cycle detected")

return dist

7. 파이썬 구현 예시

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

# Step 1: relaxation V-1 times
for _ in range(V - 1):
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

# Step 2: check negative cycle
for u, v, w in edges:
    if dist[u] != INF and dist[u] + w < dist[v]:
        raise ValueError("Negative cycle detected")

return dist

8. 시간 복잡도

각 반복에서 모든 간선을 검사: O(E)

반복은 V - 1번: O(VE)

음수 사이클 검사: O(E)

총 시간 복잡도: O(VE)

9. 핵심 요약

간선 기반 relaxation 알고리즘

각 간선은 (u, v, w) 형태여야 한다

V - 1번 relaxation으로 모든 최단 경로 확정

음수 사이클 검사 가능

10...

이해하는데 2시간이나 썻다 재귀가 아닌데 어떻게 모든 경우의 수를 따지지 생각했는데 간단한거 였다. 하;