플로이드 워셜 C++

플로이드 워셜 알고리즘은 그래프의 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘입니다.

 

한 노드를 중간 지점으로 두고 나머지 노드 간의 거리를 해당 중간 노드를 거쳐갈 때 업데이트를 시킵니다.

 

점화식은 다음과 같습니다.

D[a][b] = min(D[a][b], D[a][k], D[k][b])

a : start, b : finish, k : middle 

 

주의할 점은 loop 3번을 돌 때 중간노드를 첫 번째 loop 로 잡아야 하는 점입니다.

 

아래와 같은 그래프에서 플로이드 워셜 알고리즘 코드는 다음과 같습니다.

 

 

#include <iostream>

using namespace std;

#define INF 987654321

void floyd_warshall(int graph[5][5], int nodeNum)
{
	// mid : 중간 노드 
	// start : 출발 노드 
	// finish : 도착 노드 
	for(int mid = 0; mid < nodeNum; mid++) {
		for(int start = 0; start < nodeNum; start++) {
			for(int finish = 0; finish < nodeNum; finish++) {
				// 점화식 : d_ab = min(d_ab, d_ak + d_kb)
				// a = start, b = finish, k = mid 
				graph[start][finish] = min(graph[start][finish], graph[start][mid] + graph[mid][finish]); 
			}
		}
	} 
}

int main()
{
	int nodeNum = 5;
	int graph[5][5] = {
		{0,   3,   5, INF, INF},
		{3,   0,  10,   7,   2},
		{5,  10,   0, INF,   6},
		{INF, 7, INF,   0,   3},
		{INF, 2,   6,   3,   0},
	};
	
	floyd_warshall(graph, nodeNum);
	
	for(int i = 0; i < nodeNum; i++) {
		cout << "node " << i << " : ";
		for(int j = 0; j < nodeNum; j++) {
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}
}