안녕하세요. 소리입니다 👋
이번 글에서는 다익스트라에 이어 벨먼-포드와 SPFA 알고리즘을 가져왔어요.

---

🚀 벨먼-포드 알고리즘이란?

벨먼-포드는 다익스트라와 마찬가지로 특정 위치에서 다른 정점까지의 최단 거리를 구하는 알고리즘이에요.
그러나 다익스트라와는 달리 음수 간선이 포함된 그래프에서 사용이 가능해요.

벨먼-포드 알고리즘은 모든 간선을 반복해서 확인하며 경로를 찾아요.
이때, 어떤 그래프에서 최단 경로의 가장 긴 경우는 모든 정점을 한 번씩 거치는 경로라는 점을 이용해요.

• 시간 복잡도: $O(VE)$
  V: 정점 개수 E: 간선의 수

과정

1. 최단 거리 배열 초기화
   • 시작 정점의 거리를 0으로 설정합니다.
   • 나머지 모든 정점은 무한대($\infty$)로 초기화합니다.
2. 그래프의 모든 간선을 $(V-1)$번 반복해서 최단 경로를 갱신
   • 그래프의 모든 간선에 대해 간선을 이용할 때 거리가 짧아지는지 확인합니다.
3. 음수 사이클 확인
   • 모든 간선에 대해 다시 확인했을 때 최단거리 값에 갱신이 일어난다면 음수 사이클이 존재한다고 확신할 수 있습니다.

예시

벨먼-포드 알고리즘의 첫 번째 사이클을 이미지와 함께 살펴볼게요.
시작 정점을 A로 두고 설명할게요.

모든 간선을 차례대로 방문하면서 갱신되는 최단거리 값은 아래처럼 변해요.

	정점 A	정점 B	정점 C	정점 D	정점 E
초깃값	0	$\infty$	$\infty$	$\infty$	$\infty$
$A→B$	0	1	$\infty$	$\infty$	$\infty$
$A→C$	0	1	4	$\infty$	$\infty$
$B→D$	0	1	4	6	$\infty$
$B→E$	0	1	4	6	3
$C→B$	0	1	4	6	3
$C→D$	0	1	4	6	3
$E→C$	0	1	-1	6	3
$E→D$	0	1	-1	6	3

이 작업을 ($V-1$)번 반복하면 최단거리 값은 다음처럼 나와요.

	정점 A	정점 B	정점 C	정점 D	정점 E
최종값	0	1	-1	0	3

음수 사이클 존재 여부는 최단 경로 계산이 완료된 후 한번 더 확인했을 때, 갱신이 진행되는 정점이 있는지 확인해서 파악할 수 있어요.
위 예시에서는 음수 사이클이 없어 새로운 경로로 갱신이 일어나지 않아요.

구현

Python

def bellman_ford(graph, start):
    # 최단 거리 배열 초기화
    dist = [math.inf for _ in range(len(graph))]
    prev = [None for _ in range(len(graph))]

    dist[start] = 0

    # (V - 1)번 반복하여 최단 경로 배열 갱신
    for _ in range(1, len(graph)):
        # 모든 간선에 대해 갱신 시도
        for v in range(len(graph)):
            # 간선의 출발점이 한 번도 갱신이 없었다면, 인접 정점의 거리 갱신이 일어나지 않음
            if dist[v] == math.inf:
                continue

            # 인접 정점의 최단 경로 배열 갱신 시도
            for (next, cost) in graph[v]:
                if dist[next] > dist[v] + cost:
                    dist[next] = dist[v] + cost
                    prev[next] = v

    # 음수 사이클 확인
    for v in range(len(graph)):
        if dist[v] == math.inf:
            continue
        for (next, cost) in graph[v]:
            if dist[next] > dist[v] + cost:
                return None

    # 경로가 필요하다면 prev 반환
    return dist

Rust

fn bellman_ford(graph: &Vec<Vec<(usize, i32)>>, start: usize) -> Option<Vec<i32>> {
    // 최단 거리 배열 초기화
    let mut dist = vec![i32::MAX; graph.len()];
    let mut prev = vec![None; graph.len()];
    
    dist[start] = 0;
    
    // (V - 1)번 반복하여 최단 경로 배열 갱신
    for _ in 1..graph.len() {
        // 모든 간선에 대해 갱신 시도
        for v in 0..graph.len() {
            // 간선의 출발점이 한 번도 갱신이 없었다면, 인접 정점의 거리 갱신이 일어나지 않음
            if dist[v] == i32::MAX {
                continue;
            }
            
            // 인접 정점의 최단 경로 배열 갱신 시도
            for (next, cost) in &graph[v] {
                if dist[*next] > dist[v] + cost {
                    dist[*next] = dist[v] + cost;
                    prev[*next] = Some(v);
                }
            }
        }
    }

    // 음수 사이클 확인
    for v in 0..graph.len() {
        if dist[v] == i32::MAX {
            continue;
        }
        for (next, cost) in &graph[v] {
            if dist[*next] > dist[v] + cost {
                return None;
            }
        }
    }
    
    // 경로가 필요하다면 prev 반환
    Some(dist)
}

🔨 개선된 벨먼-포드, SPFA 알고리즘

혹시 벨먼-포드 알고리즘의 동작 과정을 볼 때, 불필요한 계산이 있었다는 생각이 드셨나요?
SPFA 알고리즘은 벨먼-포드의 불필요한 부분을 최적화한 알고리즘이에요.

만약 그래프가 단절 그래프 형태일 때 모든 간선을 살펴보는 것은 비효율적일 거예요.
더불어, 시작점 멀리에 있는 간선을 확인하는 것도 비효율적이죠.

SPFA 알고리즘은 벨만-포드에 너비 우선 탐색(BFS)을 적용해 위에서 언급한 문제를 해결했어요.

시간 복잡도(최적·평균)	시간 복잡도(최악)
$O(V+E)$	$O(VE)$

V: 정점 개수 E: 간선의 수

과정

1. 최단 거리 배열 초기화
   • 시작 정점의 거리를 0으로 설정합니다.
   • 나머지 모든 정점은 무한대($\infty$)로 초기화합니다.
2. 시작 정점을 시작으로 그래프 BFS 탐색
   • 현재 위치에서 인접 정점의 거리를 갱신합니다.
   • 갱신된 인접 정점이 방문 큐에 없다면 추가합니다.
3. 음수 사이클 확인
   • 만약 2번 과정 진행 중 특정 정점이 $V$번 방문되었다면, 음수 사이클이 존재한다고 확신할 수 있습니다.

구현

Python

def spfa(graph, start):
    # 최단 거리 배열 초기화
    dist = [math.inf for _ in range(len(graph))]
    prev = [None for _ in range(len(graph))]

    # 탐색 큐 및 방문 횟수 기록 배열 초기화
    que = deque()  # from collections import deque
    in_que = [False for _ in range(len(graph))]
    cnt = [0 for _ in range(len(graph))]

    dist[start] = 0
    que.append(start)
    in_que[start] = True

    # BFS 탐색
    while que:
        v = que.popleft()
        cnt[v] += 1
        in_que[v] = False

        # 음수 사이클이 존재하는 경우
        if cnt[v] >= len(graph):
            return None

        # 인접 정점의 최단 경로 배열 갱신 시도
        for (next, cost) in graph[v]:
            if dist[next] > dist[v] + cost:
                dist[next] = dist[v] + cost
                prev[next] = v

                # 갱신된 정점이 큐에 없다면 큐에 삽입
                if not in_que[next]:
                    que.append(next)
                    in_que[next] = True

    # 경로가 필요하다면 prev 반환
    return dist

Rust

fn spfa(graph: &Vec<Vec<(usize, i32)>>, start: usize) -> Option<Vec<i32>> {
    // 최단 거리 배열 초기화
    let mut dist = vec![i32::MAX; graph.len()];
    let mut prev = vec![None; graph.len()];

    // 탐색 큐 및 방문 횟수 기록 배열 초기화
    let mut queue = VecDeque::new();
    let mut in_queue = vec![false; graph.len()];
    let mut cnt = vec![0; graph.len()];

    dist[start] = 0;
    queue.push_back(start);
    in_queue[start] = true;

    // BFS 탐색
    while let Some(v) = queue.pop_front() {
        cnt[v] += 1;
        in_queue[v] = false;

        // 음수 사이클이 존재하는 경우
        if cnt[v] >= graph.len() {
            return None;
        }

        // 인접 정점의 최단 경로 배열 갱신 시도
        for (next, cost) in &graph[v] {
            if dist[*next] > dist[v] + cost {
                dist[*next] = dist[v] + cost;
                prev[*next] = Some(v);

                // 갱신된 정점이 큐에 없다면 큐에 삽입
                if !in_queue[*next] {
                    queue.push_back(*next);
                    in_queue[*next] = true;
                }
            }
        }
    }

    // 경로가 필요하다면 prev 반환
    Some(dist)
}

📊 최단 경로 알고리즘의 비교

지금껏 세 종류의 최단 경로 계산 알고리즘을 알아봤어요.
세 가지의 시간과 장단점을 정리했어요.

	시간 복잡도(최적·평균)	시간 복잡도(최악)	음수 가중치 간선 처리
다익스트라	$O((V+E)logV)$	$O((V+E)logV)$	불가능
벨먼-포드	$O(VE)$	$O(VE)$	가능
SPFA	$O(V+E)$	$O(VE)$	가능

V: 정점 개수 E: 간선의 수

평균적으로는 SPFA가 가장 빠른 알고리즘이지만, PS에서는 SPFA의 최악 케이스를 포함하는 경우가 있어 최악의 경우를 가정하고 문제 해결 방법을 설계해야 해요.

---

지금까지 벨먼-포드와 SPFA 알고리즘에 대해 알아봤습니다.
다익스트라와 마찬가지로 실생활에 밀접한 알고리즘이어서, 잘 익혀두는 것이 좋아요.
최단 경로를 구할 때 어떤 알고리즘이 유리한지 판단할 수 있다면, 앞으로 문제 해결에 큰 도움이 될 거예요.

다음에도 흥미롭고 유익한 내용으로 찾아올게요! 😁