반응형
플로이드-워셜 알고리즘
플로이드-워셜 알고리즘 이란?
- 모든 정점 사이의 최단 경로, 최단 거리를 구하는 알고리즘
- 다익스트라는 한 정점에서 다른 정점까지의 최단거리이지만,
플로이드-워셜은 모든 정점들 사이의 최단 거리를 구하는 것이다.
- 구현이 간단하다.
- 구현을 위하여 행렬을 사용한다.
- 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]);
}
}
}
}
반응형
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
최소 비용 신장 트리 - 프림(Prim) 알고리즘 (0) | 2020.11.23 |
---|---|
최소 비용 신장 트리 - 크루스칼(Kruskal) 알고리즘. (0) | 2020.11.23 |
최단 거리 알고리즘 - 벨만-포드(Bellman-Ford) 알고리즘 (0) | 2020.11.23 |
최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra) (0) | 2020.07.16 |
탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS) (0) | 2020.06.22 |
댓글