최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜 알고리즘

 

플로이드-워셜 알고리즘 이란?

 

 - 모든 정점 사이의 최단 경로, 최단 거리를 구하는 알고리즘

 

 - 다익스트라는 한 정점에서 다른 정점까지의 최단거리이지만,

   플로이드-워셜은 모든 정점들 사이의 최단 거리를 구하는 것이다.

 

 - 구현이 간단하다.

 

 - 구현을 위하여 행렬을 사용한다.

 

 - N개의 정점이 존재할 때 O($N^3$)의 시간복잡도를 가진다.

 

---

 

플로이드-워셜 알고리즘 실행 과정

 

 - 1. 행렬의 초기값을 그래프의 인접 행렬과 같은 값으로 설정한다.

 

 - 2. 정점i 에서 정점j까지의 최단 경로를 결정할 때 거치는 중간값을 모두 탐색하여 최단 경로를 찾는다.

 

 - 3. 모든 정점을 탐색하면 종료한다.

 

 - Dist[i][j]를 i에서 j까지 최단 경로라 하면, Dist[i][j] = min(Dist[i][j],Dist[i][k]+Dist[k][j])의 과정을 모두 탐색한다.

 

 

 - 중간에 거쳐야 할 경로를 고정해서 탐색함으로써 중간 경로로 갈 수 있는 경로를 탐색한다.

---

 

플로이드-워셜 코드(C++)

 

 

void Floyd(vector<vector<pair<int, int>>> &g)
{
	
	for (int i = 0; i < g.size(); i++)
	{
		for (int j = 0; j < g[i].size(); j++)
			dist[i][g[i][j].first] = g[i][j].second;
	}
	// v는 노드의 개수
    // 순서는 무조건 경유지 부터 해야 한다.
    // 즉, k가 가장 먼저 나와야 한다.
	for (int k = 0; k < v; k++)
	{
		for (int i = 0; i < v; i++)
		{
			for (int j = 0; j < v; j++)
			{

				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

			}
		}
	}

}