플로이드 와샬 알고리즘

다익스트라 알고리즘은 한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘인데 반해 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 

 

다익스트라 알고리즘은 최소의 비용을 가지는 간선을 선택하였다면, 플로이드 와샬 알고리즘은 특정 노드를 거쳐가는 경로에 대한 알고리즘이다.

 

 

그래프

 

그래프가 위와 같이 형성되었다고 가정하면 소스코드는

 

#include <iostream>

#define INF 1e9	
using namespace std;

int number = 4;
int a[4][4] = {
	{0, 5, INF, 8},
	{7, 0, 9, INF},
	{2, INF, 0, 4},
	{INF, INF, 3, 0}
};

void floyd() {
	int result[4][4];

	// 결과값을 담는 배열 result를 초기화
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			result[i][j] = a[i][j];
		}
	}

	for (int k = 0; k < number; k++) {
		for (int i = 0; i < number; i++) {
			for (int j = 0; j < number; j++) {
				if (result[i][k] + result[k][j] < result[i][j]) {
					result[i][j] = result[i][k] + result[k][j];
				}
			}
		}
	}

	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			printf("%2d ", result[i][j]);
		}
		printf("\n");
	}

}

int main() {
	floyd();

	return 0;
}