그래프 최단 경로 찾기 . 벨만-포드, 다익스트라, 플로이드-워셜 알고리즘

 

---

벨만-포드 알고리즘(Bellman-Ford algorithm)은 시작노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다.

 

길이(가중치)가 음수인 사이클을 포함하지 않는 모든 그래프를 처리할 수 있다.

또한 길이(가중치)가 음수인 사이클을 포함하는 지도 확인할 수 있다.

 

시작노드의 거리는 0으로 그리고 나머지 노드까지의 거리는 무한대로 초깃값을 설정하고, 이 값들을 차례로 줄여나가면서 더는 줄일 수 없을때 까지 반복한다.

 

알고리즘은 n-1번 진행되며, 라운드마다 m개의 간선을 처리하기 때문에 시간복잡도는 O(nm)이다.

---

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
#define INF  99999999;

int main() {
	// 간선 리스트 (시작노드, 도착노드, 가중치)
	vector<tuple<int, int,int>> edges;
	edges.push_back({ 0,1,2 });
	edges.push_back({ 0,2,3 });
	edges.push_back({ 0,3,7 });
	edges.push_back({ 1,3,3 });
	edges.push_back({ 1,4,5 });
	edges.push_back({ 2,3,1 });
	edges.push_back({ 3,4,2 });

	int n = 5; // 노드 갯수
	int distance[5];

	//거리 초깃값은 무한대
	for (int i = 0; i < n; i++) 
		distance[i] = INF;
	distance[0] = 0; // 시작노드 초깃값은 0

	for (int i = 1; i <= n - 1; i++) {
		for (auto e : edges) {
			int a, b, w;
			tie(a, b, w) = e;
			distance[b] = min(distance[b], distance[a] + w);
		}
	}

	//결과 확인
	for (auto d : distance)
		cout << d << ' ';
}

실행결과는 0 2 3 4 6

---

만약 한 라운드를 진행하는 동안 거리가 줄어드는 것이 없다면 알고리즘을 종료해도 된다.

또한 SPFA(Shortest Path Faster Algorithm, 좀더 빠른 최단 경로 알고리즘)도 존재한다. 거리를 줄이는 데 사용될 수 있는 노드를 별도의 큐로 관리하며, 그 노드만을 처리하기때문에 조금 더 효율적으로 탐색할 수 있다.

 

-> 만약 그래프의 음수 사이클이 포함되는 지가 궁금하다면, 알고리즘을 n번 (기존 n-1번) 진행하면 된다.

만약 마지막 라운드에서도 거리가 줄어드는 경우가 생긴다면, 그래프 내에 음수 사이클이 존재한다는 것이다.

 

---

다익스트라 알고리즘(Dijkstra's algorithm)은 마찬가지로 시작노드에서부터 모든 노드까지의 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 음수인 간선이 없는 경우에만 사용가능하지만, 벨만-포드 알고리즘보다 효율적이다.

 

각 단계에서는 아직 처리하지 않은 노드 중 가장 작은 노드를 찾고 그 노드에서 시작하는 모든 간선을 살펴보며 거리를 줄일 수 있다면 줄인다. 음수 간선이 없다는 점을 이용하여, 모든 간선을 한번만 처리하기 때문에 매우 효율적이다.

 

---

인접 리스트의 형태로 정보가 저장된 그래프를 우선순위 큐를 이용하여 구현한 다익스트라 알고리즘

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF  99999999;

int main() {

	//인접 리스트
	vector<pair<int,int>> adj[5];
	adj[0].push_back({ 2,5 });
	adj[0].push_back({ 3,9 });
	adj[0].push_back({ 4,1 });
	adj[1].push_back({ 2,2 });
	adj[2].push_back({ 3,6 });
	adj[3].push_back({ 4,2 });

	adj[2].push_back({ 0,5 });
	adj[3].push_back({ 0,9 });
	adj[4].push_back({ 0,1 });
	adj[2].push_back({ 1,2 });
	adj[3].push_back({ 2,6 });
	adj[4].push_back({ 3,2 });

	// 우선순위 큐는 최대 원소값이 우선이지만, 최소를 찾아야하기때문에 -d의 형태로 저장
	priority_queue<pair<int, int>> q;
	int n = 5; // 노드 갯수
	int distance[5]; // 거리를 저장
	bool processed[5]; // 노드를 처리했는지 여부를 저장

	//거리 초깃값은 무한대
	for (int i = 0; i < n; i++) {
		distance[i] = INF;
		processed[i] = false;
	}
	distance[0] = 0; // 시작노드 초깃값은 0

	q.push({ 0, 0}); // (-d,x) 0번 노드까지의 거리가 0 
	while (!q.empty()) {
		int a = q.top().second;
		q.pop();
		if (processed[a]) continue;
		processed[a] = true;
		for (auto u : adj[a]) {
			int b = u.first, w = u.second;
			if (distance[a] + w < distance[b]) {
				distance[b] = distance[a] + w;
				q.push({ -distance[b], b });
			}
		}
	}

	//결과 확인
	for (auto d : distance)
		cout << d << ' ';
}

실행결과는 0 7 5 3 1

 

---

플로이드-워셜 알고리즘(Floyd-Warshall algorithm)은 구현이 간단하지만, 시간복잡도가 O(n^3)으로 크기때문에 그래프의 크기가 작을 때 사용한다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF  99999999;

int main() {
	//인접 행렬
	int adj[5][5];
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			adj[i][j] = 0;

	int dist[5][5];

	adj[0][1] = 5;
	adj[0][3] = 9;
	adj[0][4] = 1;
	adj[1][0] = 5;
	adj[1][2] = 2;
	adj[2][1] = 2;
	adj[2][3] = 7;
	adj[3][0] = 9;
	adj[3][2] = 7;
	adj[3][4] = 2;
	adj[4][0] = 1;
	adj[4][3] = 2;

	// 거리행렬의 초깃값
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (i == j) dist[i][j] = 0;
			else if (adj[i][j]) dist[i][j] = adj[i][j];
			else dist[i][j] = INF;
		}
	}
	// 플로이드 워셜 알고리즘
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			for (int k = 0; k < 5; k++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

	//결과 확인
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++)
			cout << dist[i][j] << ' ';
		cout << endl;
	}
}