플로이드 와샬 (Floyd Warshall)

플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘.

 

 

<전체적인 알고리즘>

1. 시작점에서 목적지로 가는 경로에 한 정점을 지나갈 때 거리가 더 짧아지면 해당 경로로 갱신한다.

2. 모든 시작점과 모든 목적지 쌍에 대해 1을 반복한다.

 

<시간 복잡도>

당연히 O(n^3)이다. 그냥 코드만 봐도 3중첩 for문이다. 

 

<경로 구하는 알고리즘>

갱신될 때 마다 지나야 하는 k를 저장해두면 되돌아가면서 경로를 찾을 수 있다.

 

<전체 코드>

 

#include<iostream>

using namespace std;

int INF = 987654321;
int PAD = 0;
int dist[6][6] =          // 그래프 셋팅 //직관적이기 쉽게 index0은 패딩으로 채움
{
	{PAD,PAD,PAD,PAD,PAD,PAD},
	{PAD,0,6,8,INF,2},
	{PAD, INF,0,INF,5,INF},
	{PAD ,4,INF,0,INF,1},
	{PAD ,11,INF,INF,0,INF},
	{PAD ,INF,INF,INF,3,0}
};
int n = 5;
int P[5][5];

void Floyd()
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{

				if (dist[i][j] > dist[i][k] + dist[k][j])  //k노드를 거치는게 빠르면 갱신
				{
					dist[i][j] = dist[i][k] + dist[k][j];
					P[i][j] = k;   //i에서j로 가는 최단경로 갱신되는 k노드 저장.
				}

			}
		}
	}
}

void path(int start, int end)
{
	if (P[start][end] == 0)return;

	path(start, P[start][end]);
	cout << P[start][end] << " ";
	path(P[start][end], end);
}
void PATH(int start, int end)
{
	cout << start << " ";
	path(start, end);
	cout << end << " ";
}

int main()
{
	Floyd();

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i != j)
			{
				printf("%d -> %d   최단 거리 : %2d", i, j, dist[i][j]);
				printf("        최단 경로 : ");
				PATH(i, j); // i 에서 j로 가는 최단 경로
				printf("\n");
			}
		}
	}

	return 0;
}

 

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.