벨판-포드의 최단 경로 알고리즘

벨판-포드

💡

다익스트라의 음수 간선 문제를 해결한 최단 경로 알고리즘

다익스트라와의 차이

벨판-포드는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄이는 방식

---

동작 과정

upper[]

• 시작지점으로부터 각 정점까지 최단 거리의 상한

• 시작점→시작점의 거리는 0

• 나머지는 매우 큰 수로 저장

• 시작점이 아닌 임의의 두 지점 u, v
  • dist[u]
    • 시작지점 → u 까지의 최단 거리
  • dist[v]
    • 시작지점 → v 까지의 최단 거리
  • 이때, 다음이 성립한다.
    • dist[v] ≤ dist[u] + w(u, v)
    • dist[u] ≤ upper[u]
    • upper[u] + w(u, v) ≤ upper[v]

---

종료 조건과 정당성의 증명

어떻게 upper[] 의 값을 dist[] 값으로 만들 수 있을까?

dist[u]가 s→a→b→c→u 를 거치는 비용이라고 하자.

초기 upper[s]는 0이다.

이 때 최초의 upper값들은 다음과 같다.

node	upper[node]
s	0
a	∞
b	∞
c	∞
u	∞

이후 모든 간선을 순회하면서 한 번씩 완화를 해보자

a의 경우

upper[a] ≤ upper[s] + w(s, a) 이고, upper[s]=0 이므로 다음이 성립한다.

upper[a] ≤ w(s, a)

이 때 upper[a] 는 ∞이므로 upper[a] = w(s, a)가 된다.

node	upper[node]
s	0
a	w(s, a)
b	w(s, b) ? w(s, b) : ∞
c	w(s, c) ? w(s, c) : ∞
u	w(s, u) ? w(s, u) : ∞

또 모든 간선을 순회하면서 한 번씩 완화를 해보자

만약 s에서 b로 가는 경로가 있다고 해보자

upper[b] = w(s, b) ≤ upper(a) + w(a, b)

w(s, b)값이 더 작다면, 위 그림의 경로가 나오지 않으므로

upper[b] = upper(a) + w(a, b)

node	upper[node]
s	0
a	w(s, a)
b	upper(a) + w(a, b)
c	w(s, c) ? w(s, c) : ∞
u	w(s, u) ? w(s, u) : ∞

위 과정을 반복하게 되면 u까지의 최단경로가 나오게 된다.

반복 도중 모든 간선을 돌았는데 갱신이 되지 않는다면, 종료한다.

N번 반복을 하게 되면, N개 이하의 간선을 사용한 최단경로를 구할 수 있다.

---

음수 사이클의 판정

다익스트라 알고리즘과 큰 차이점을 보이는 부분이다.

이를 어떻게 판정하는지 살펴보자

위 알고리즘대로 진행을 하게 된다면, 무한반복하며 음수 사이클이 만들어질 수 밖에 없다.

|V|개의 정점을 가진 그래프에서 가장 많은 간선을 거치는 방법은 |V|-1번 간선을 거치는 것이다.

즉 그래프는 다음과 같다.

하지만 음수 간선을 가진다면, |V|번째에도 최단경로가 생길 것이다. (계속해서 거리가 줄어드므로)

결론: |V|번째 반복 시에 최단 경로가 갱신된다면 음수 사이클이 존재!

---

구현

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class 벨만_포드 {
    // 정점의 개수
    static int V;

    // 그래프의 인접 리스트
    static List<List<Pair>> adj;

    static class Pair {
        int index, cost;

        public Pair(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }
    }

    static List<Integer> bellmanFord(int src) {
        // 모든 경로의 최단 거리 상한을 무한대로
        List<Integer> upper = new ArrayList<>();
        Collections.fill(upper, Integer.MAX_VALUE);

        // 시작 지점 -> 시작 지점은 0
        upper.set(src, 0);

        // 경로가 갱신 되었는지 확인
        boolean updated = false;

        // 반복은 V번한다.
        for (int i = 0; i < V; i++) {
            updated = false;
            // 시작지점
            for (int here = 0; here < V; here++) {
                // 시작지점에서 갈 수 있는 곳
                for (int j = 0; j < adj.get(here).size(); j++) {
                    int there = adj.get(here).get(j).index;
                    int cost = adj.get(here).get(j).cost;

                    // 갱신작업
                    // s->there > s->here->there 인 경우 갱신
                    if (upper.get(there) > upper.get(here) + cost) {
                        // 갱신 성공 처리
                        updated = true;
                        upper.set(there, upper.get(here) + cost);
                    }
                }
            }

            // 현재 반복 때 아무런 갱신이 없다면 음수사이클이 없고, 최적 경로를 찾았다.
            if (!updated) {
                break;
            }
        }

        // V번째에 갱신이 생긴 경우
        if (updated) {
            upper.clear();
        }

        return upper;
    }

    public static void main(String[] args) {

    }
}

---

시간 복잡도 분석

가장 밖의 반복문은 |V|번 반복

그 안의 반복문은 모든 간선을 순회하므로 |E|번 반복한다.

따라서 시간 복잡도는 O(|V||E|) 이다.

---

약간의 문제점

s→v의 경로가 없다고 할 때, 이를 어떻게 알 수 있을까?

upper[v]의 값이 ∞가 아닐 때?

하지만 음수 간선이 있다고 생각해보자.

위 경우에 -1의 음수간선을 지난다고 하면 upper[v] < ∞ 일 것이다.

따라서 위 문제를 해결하기 위해 적당히 큰 값 M을 이용하여 ∞-M 미만인지 비교해야한다.

---

Uploaded by N2T