최단 경로 알고리즘(1)

이 글에서는 최단 경로를 구하는 알고리즘으로 무엇이 있는지, 대강 어떤 원리로 굴러가는지만 소개한다.

Floyd-Warshall

첫 번째 주자는 플로이드-워셜이다. 가장 구현이 간단하며 모든 정점에서 모든 정점까지의 최단 경로를 구할 수 있다는 특징이 있다.

기본적인 원리는 a->b로 가는 거리와 a->?->b로 거쳐가는 거리 중 무엇이 더 짧은지 갱신하는 것이다.

대략적인 구현은 INF(나올 수 없는 큰 수)값으로 초기화를 해주고나서 주어진 간선들을 배열에 넣어주고 나서 아래의 반복문을 돌려주면 된다.

// i->j 가 짧은지 i->k->j가 짧은지를 비교하여 갱신한다.
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
        }
    }
}

시간 복잡도가 $O(V^3)$이기에 정점의 개수가 적은 그래프에서 사용된다.

Dijkstra

두 번째로 소개할 알고리즘은 다익스트라이다. 최단 경로 알고리즘 중에 대표적인 알고리즘이다. 플로이드-워셜과는 달리 한 정점에서 모든 정점까지의 최단 경로만 구할 수 있다. 대신 시간 복잡도가 $O(NlogN)$이다.

여기서 그러면 그냥 다익스트라를 $N$번 돌려서 모든 정점에서 모든 정점까지의 최단거리를 더 빠르게 구할 수 있지 않냐는 의문이 생길 수 있다. 사실 정확한 시간 복잡도는 $O(ElogV)$이고, $E\left(1\leq E\leq \frac{V\times (V+1)}{2}\right)$의 범위를 보면 $O(V^3logV)$이 되기에.. 오히려 시간적인 측면은 비효율적이다.

다익스트라는 아래와 같이 굴러간다.

1. 시작 정점을 최단 경로 집합 $S$에 넣는다.
2. 집합 $S$에서 다른 정점으로 갈 수 있는 최단 경로를 선택하여 해당 정점을 집합 $S$에 넣는다. 이를 진행하며 최단 경로를 갱신한다.
3. 2를 모든 정점을 방문할 때까지 반복한다.

시작 정점이 1이라고 하고, 정점은 1부터 4까지 있다고 하자.
1에서 갈 수 있는 정점이 2, 3이 있고 각각 거리가 5, 3이다. 이 경우 2번에 의해 정점 3이 택해진다. $({1, 3}\in S)$

1에서 갈 수 있는 정점은 2이고 거리는 5이다. 3에서 갈 수 있는 정점은 1, 2, 4가 있고 각각 거리가 2, 4, 1이다. 정점 1은 이미 집합에 포함되어 있으므로 제외한다. 다른 정점으로 가는 최단 경로는 거리가 1인 정점 4로 가는 것이다. $({1, 3, 4}\in S)$

아래서부터는 정점(거리)로 표기하도록 하겠다.
1에서 갈 수 있는 정점은 2(5)
3에서 갈 수 있는 정점은 2(2)
4에서 갈 수 있는 정점은 1(3), 2(4)이다.
3에서 2로 가는 것이 거리가 2로 최소이다. $({1, 2, 3, 4}\in S)$

집합에 모두 포함이 되었으므로 모든 정점을 방문한 것이고, 종료한다.

이렇게 1에서 다른 모든 정점까지의 최단 경로를 구할 수 있다.

구현을 아래와 같다. c++에서 priority_queue는 max_heap이기에 가중치에 -를 붙여서 구현해 주었다. 이것이 싫다면 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;와 같이 min_heap으로 구현하면 된다.

priority_queue<pair<int, int>> pq;
vector<int> dist(n + 1); fill(dist + 1, dist + n + 1, INF);

dist[s] = 0; pq.push({ 0, s_node });
while (!pq.empty()) {
    int cost = -pq.top().ff;
    int x = pq.top().ss;
    pq.pop();

    for (int i = 0; i < v[x].size(); i++) {
        int nx = v[x][i].first;
        int ncost = v[x][i].second + cost;
        if (dist[nx] > ncost) {
            dist[nx] = ncost;
            pq.push({ -dist[nx], nx });
        }
    }
}

여기까지는 음수 가중치를 가진 사이클이 존재하지 않는 경우에 사용할 수 있는 최단 경로 알고리즘이었다. 다음 글에서는 음수 가중치를 가진 사이클이 존재하여도 최단 경로를 구할 수 있는 벨만-포드와 그 진화 버전인 SPFA를 다루도록 하겠다.