최단 경로 알고리즘(2)

최단 경로 알고리즘(1) - floyd-warshall / dijkstra
이전 글과 달리 이번 글에서는 가중치가 음수인 간선에 대해서도 (가중치가 음수인 cycle이 생기는 그래프) 최단 경로를 구할 수 있는 알고리즘을 소개한다.

Bellman Ford

첫 번째로 알아볼 벨만-포드 알고리즘이다. 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며 간선의 가중치가 음수일 때도 경로를 구할 수 있다는 특징을 가지고 있다.

벨만-포드 는 아래와 같이 굴러간다.

1. 모든 간선을 확인하면서 최단 경로를 갱신한다.
2. 1.을 $V$번 반복한다. 만약 $V$번째에서도 최단 경로를 갱신하려 한다면 음수 사이클이 존재한다는 것이다.

$V$번째에서도 갱신 시도가 있을 때 음수 사이클이 존재한다는 것의 이유는 $V-1$번 반복을 완료한 단계에서 모든 노드에 대해 최단 경로가 결정되기 때문이다.

시간 복잡도는 $O(VE)$이다.

int n, m, dist[MAXN]; // dist는 INF로 초기화
vector<pair<pair<int, int>, int>> v;

void bellman_ford() {
    bool flag = 0;
    dist[1] = 0; // 시작 정점 갱신

    for (int i = 0; i < n; i++) { // V번 돌려본다
        for (const auto& [dir, cost] : v) { // 모든 간선을 확인 
            if (dist[dir.ff] != INF && dist[dir.ss] > dist[dir.ff] + cost) {
                if (i == n - 1) { // V번째에서도 갱신 시도가 있다면 음수 사이클 존재
                    flag = 1;
                    break;
                }
                dist[dir.ss] = dist[dir.ff] + cost;
            }
        }
    }
}

SPFA(Shortest Path Faster Algorithm)

두 번째로 소개하는 SPFA 는 이름에서도 알 수 있듯이 더 빠른 최단 경로 알고리즘이다. 벨만-포드 를 최적화한 버전이다.

기본적으로 시간 복잡도가 $O(VE)$이지만 실제로는 $O(V+E)$나 $O(E)$에 돌아간다고 생각해도 된다.

벨만-포드 와의 차이점이라고 한다면 업데이트 하는 간선에서 찾을 수 있다.
벨만-포드 가 모든 간선을 업데이트 한다면,
SPFA 는 갱신된 정점과 연결된 간선에 대해서만 업데이트를 한다.

큐와 배열을 통해 이를 관리해주면 된다. 알고리즘은 BFS 와 비슷하게 돌아가기에 몇 번 쓰다보면 손에 익을 것이다.

*MCMF 에서 이 알고리즘이 사용된다. *

int dist[MAXN], vst[MAXN];
bool inQ[MAXN];
vector<pii> v[MAXN];

void SPFA() {
    inQ[1] = 1; q.push(1); dist[1] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop(); inQ[x] = 0;

        for (pii nxt : v[x]) {
            int nx = nxt.ff;
            int cost = nxt.ss;
            if (dist[nx] > dist[x] + cost) {
                dist[nx] = dist[x] + cost;
                if (!inQ[nx]) {
                    inQ[nx] = 1; q.push(nx); vst[nx]++;
                    if (vst[nx] >= n || dist[nx] < -INF) {
                        cout << -1;
                        return 0;
                    }
                }
            }
        }
    }
}

두 알고리즘 모두 BOJ 11657번: 타임머신 에서 연습할 수 있다.