Floyd Warshall 알고리즘

Floyd Warshall Algorithm

• 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구함
• 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택
• 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘 수행
• 기본적으로 다이나믹 프로그래밍 기술

 

 

위의 그래프에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열로 출력

 

0	5	INF	8
7	0	9	INF
2	INF	0	4
INF	INF	3	0

 

위 테이블은 현재까지 계산된 최소 비용

이러한 이차원 배열을 반복적으로 갱신해 최종적으로 모든 최소비용을 구해야함
반복의 기준은 거쳐가는 정점

 

1. 노드 1을 거쳐가는 경우: 색칠된 6가지 공간 갱신

0	5	INF	8
7	0	9	INF
2	INF	0	4
INF	INF	3	0

 

이 때, X에서 Y로 가는 최소 비용과 X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용 비교

더 빠른 경우로 최소 비용 갱신

 

• D[2,3]의 값은 D[2,3]과 (D[2,1] + D[1,3]) 중 더 작은 값으로 갱신

0	5	INF	8
7	0	9	15
2	7	0	4
INF	INF	3	0

 

2. 노드 2를 거쳐가는 경우: 색칠된 6가지 공간 갱신

0	5	14	8
7	0	9	15
2	7	0	4
INF	INF	3	0

 

3. 같은 방식으로 노드 3, 4에 대해 갱신

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

 

코드 구현

#include<iostream>
#include<cstdio>

using namespace std;

int number = 4;
int INF = 1000000000;

//자료 배열 초기화
int a[4][4] = {
	{0,5,INF,8},
	{7,0,9,INF},
	{2,INF,0,4},
	{INF,INF,3,0}
};


void floydWarshall() {
	//결과 그래프 초기화
	int d[4][4];

	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++) {
			printf("%3d ", d[i][j]);
		}
		cout << '\n';
	}
}


int main(void) {
	floydWarshall();
}