[알고리즘] 최단거리 (다익스트라, 벨만포드, 플로이드와셜 알고리즘) Dijkstra, Bellman-Ford, Floyd-Warshall Algorithm

📁 최단거리문제

보통 시작노드부터 도착노드까지의 최단경로를 구하는 형식의 문제이다. MST에서 알 수 있듯이 최단경로는 절대 사이클을 포함하지 않는다. 최단거리 문제는 가중치 유무에 따라, 가중치가 있을 경우엔 가중치의 음양에 따라 알맞은 알고리즘을 사용한다.

• 양의 가중치만 있을 때 : 다익스트라 알고리즘(Dijkstra's Algorithm)
• 음의 가중치만 있을 때 : 벨만포드 알고리즘(Bellman-Ford Algorithm)
• n 대 n의 최단거리를 모두 구하고 싶을 때 : 플로이드와샬 알고리즘(Floyd-Warshall Algorithm)

📁 다익스트라 알고리즘 Dijkstra's Algorithm

에지의 가중치가 양수일 때 사용한다. 음수 가중치를 고려하지 않으므로 가중치의 합이 최단거리를 좌우한다. 

시작노드 ~ 시작노드 = 0 임을 이용해 노드를 한 칸씩 늘려가며 모든 노드에 대해 최단 거리를 계산한다. 이전 단계에서 구한 k-1 까지의 최단거리 값에 k-1 ~ k를 연결하는 에지의 가중치를 더해주며, 그 값을 계속 비교해나가는 방법이다.

시간복잡도 : 매번 최단경로를 알게 되는 노드가 하나이므로 이 과정을 총 ( V - 1 ) 번 반복한다. 각 노드에 대해 최단경로를 찾으려면 최대 V 시간이 걸리므로 O(V^2) 의 시간복잡도를 가진다. 이때 각 노드에 대해 최단경로를 찾을 때 선형탐색이 아닌 Minheap(최소힙)을 사용하면 logV 시간만에 최단거리 노드를 찾아낼 수 있다. 결국 O(V logV)까지 시간복잡도를 줄일 수 있다.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

struct edge { int to, length; };

int dijkstra(const vector<vector<edge>>& graph, int source, int target) {
    vector<int> min_distance(graph.size(), INT_MAX);
    min_distance[source] = 0;
    set<pair<int, int>> active_vertices;
    active_vertices.insert(make_pair(0, source));
    while (!active_vertices.empty()) {
        int where = active_vertices.begin()->second;
        if (where == target)
            return min_distance[where];
        active_vertices.erase(active_vertices.begin());
        for (auto ed : graph[where]) {
            if (min_distance[ed.to] > min_distance[where] + ed.length) {
                active_vertices.erase(make_pair(min_distance[ed.to], ed.to));
                min_distance[ed.to] = min_distance[where] + ed.length;
                active_vertices.insert(make_pair(min_distance[ed.to], ed.to));
            }
        }
    }
    return INT_MAX;
}

위대하신 교수님의 아주 간결한 다익스트라 구현 코드입니다..

📁 벨만포드 알고리즘 Bellman-Ford Algorithm

에지의 가중치가 음수일 때 사용한다. 음의 가중치가 존재하는 경우를 따로 고려해야 하는 이유는 최단경로에서는 사이클을 포함하면 안 되기 때문이다. MST(최소신장트리)를 공부할 때 깨달은 부분이지만, 최단경로나 최소에지를 가지는 그래프에서는 사이클을 항상 포함하지 않는다. 그런데 음수 가중치가 있다면? 사이클을 뺑뺑 돌다보면 가중치가 음으로 발산할 것이다(=나름 최소가 되어가는 거겠지) 그렇기 때문에 다익스트라를 사용할 수 없다.

비슷한 아이디어지만 아주 약간 다르다. 노드 i 부터 노드 j 의 최단거리를 구한다고 할 때, i ~ j 를 연결하는 데 에지 k개를 쓰냐 k + 1개를 쓰냐를 비교하여 에지의 개수가 k + 1 개로 많더라도 가중치합이 더 작다면 k + 1 개의 에지를 경유하는 길이 최단경로가 되는 것이다. 말이 어려운 거 같지만 결국 음의 사이클이 생기지 않도록 하는 것이다.

시간복잡도 : 매번 모든 에지를 점검해야 하며, 마찬가지로 V - 1 번 반복해야 하므로 O(V^2)의 시간복잡도를 가진다.

📁 플로이드와셜 알고리즘 Floyd-Warshall Algorithm

1개 또는 n개의 노드에 대해 최단경로를 구하는 것이 아니라, n개의 노드에서 n개의 노드까지의 모든 경우의 최단거리를 알고 싶을 때 플로이드 와셜 알고리즘을 사용한다. 노드 i ~ 노드 j 사이에 가능한 노드 k 를 모두 추가해 최단거리가 바뀌는지를 확인하는 알고리즘으로, 시간복잡도가 무려 O(V^3)이다^^

#include <iostream>
#include <climits>
using namespace std;

int graph[101][101] = { INT_MAX };

void FloydWarshall(int size) {
	for (int k = 1; k < size + 1; k++) { // Vi ~ Vk ~ Vj
		for (int i = 1; i < size + 1; i++) {
			for (int j = 1; j < size + 1; j++) {
				if (graph[i][k] && graph[k][j] && i != j) {
					graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
				}
			}
		}
	}
}