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

다익스트라 알고리즘처럼 최단 경로 구하는 알고리즘이다.

 

차이점은, 모든 정점에서 모든 정점으로의 최단 경로를 구한다는 것.

--> 다익스트라 알고리즘은 따로 게시글을 포스트할 예정입니다.

 

플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 점.

그리고 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 기반을 두고 있습니다.

 

코드를 보면, 초기 경로에 대한 값을 넣어 초기화해줍니다.

INF는 무한 값을 대체한 값입니다.

 

3중 for문으로 구현해, 최단 경로에 대한 비용을 갱신합니다.

 

#include <stdio.h>

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[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]);
		}
		printf("\n");
	}

}

int main(void)
{
	FloydWarshall();
	return 0;
}