알고리즘/알고리즘 이론
최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘
E145
2020. 11. 23. 02:21
반응형
플로이드-워셜 알고리즘
플로이드-워셜 알고리즘 이란?
- 모든 정점 사이의 최단 경로, 최단 거리를 구하는 알고리즘
- 다익스트라는 한 정점에서 다른 정점까지의 최단거리이지만,
플로이드-워셜은 모든 정점들 사이의 최단 거리를 구하는 것이다.
- 구현이 간단하다.
- 구현을 위하여 행렬을 사용한다.
- 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]);
}
}
}
}
반응형