플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

'모든 정점에서 '모든정점'으로의 최단 경로르 구하고 싶다면 플로이드 와샬 알고리즘을 사용하면 된다.

 

다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 '거져가는 정점'을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다.

 

예시 그래프

0	5	무한	8
7	0	9	무한
2	무한	0	4
무한	무한	3	0

위 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다.

 

 

X에서 Y로 가는 최소 비용 VS X에서 1로 가는 비용 + 1에서 Y로 가는 비용

 

 

노드 1을 거쳐가는 경우

0	5	무한	8
7	0	9	15
2	7	0	4
무한	무한	3	0

 

노드 2를 거치는 경우

0	5	14	8
7	0	9	15
2	7	0	4
무한	무한	3	0

위와 같이 노드 3과 노드 4에 반복해주면 된다.

.

.

.

 

0	5	11	8
7	0	9	13
2	7	0	4
5	10	3	0

#include <iostream>

using namespace std;

int number = 4;
int INF = 10000000;

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

void floydWarshall() {
	int d[number][number];
	
    // 결과 그래프를 복사
	for(int i = 0; i < number; i++) {
		for(int j = 0; j < number; j++) {
			d[i][j] = a[i][j];
		}
	}
	
	// k = 거쳐가는 노드
	for(int k = 0; k < number; k++) {
		// i = 출발 노드
		for(int i = 0; i < number; i++) {
			// j = 도착 노드
			for(int j = 0; j < number; j++) {
				if(d[i][k] + d[k][j] < d[i][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}
	
	for(int i = 0; i < number; i++) {
		for(int j = 0; j < number; j++) {
			cout << d[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int main() {
	floydWarshall();
}