개요
플로이드-와샬 알고리즘은 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.
가중치가 음인 그래프는 있지만, 음수 싸이클은 없다.
(음수 싸이클이란? 음의 가중치가 더 커서 최단 경로를 계속해서 줄일 수 있는 상태의 간선을 말함.)
벨만-포드와 음의 가중치의 최단 경로를 계산할 수 있다는 점에서 비슷하지만, 플로이드-와샬 알고리즘은 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다.
즉, 벨만-포드와 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구했다면, 플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구한다.
또한 플로이드-와샬 알고리즘은 다이나믹 프로그래밍으로 볼 수도 있다.
알고리즘
알고리즘 분류와 특징
개요에서 이야기했듯, 플로이드-와샬은 다익스트라 알고리즘과 같이 다이나믹 프로그래밍의 한 종류로도 볼 수 있다.
특징으로는, 플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 최단 거리를 구한다는 것이다.
경유지를 기준으로 최단 거리를 구한다고도 할 수 있다.
알고리즘 동작
i
행과 j
열의 원소인 (i
, j
)원소는 정점 i
로 부터 정점 j
까지의 최단 경로를 의미한다.
- 정점
i
에서 정점n
을 거쳐서 정점j
로 갈 때,n
을 거쳐 가는 것이 더 최단 경로일 경우 값을 갱신해준다. - 거쳐갈 모든 정점에 대해서 1번 과정을 수행하여 업데이트한다.
점화식: distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
동작 예시
이런 식으로 그래프와 행렬 표가 있다고 하자.
어떤 정점을 통해 갈 수 있는 정점이 아니라면 INF(무한)값으로 초기화를 해주고, 갈 수 있는 정점이라면 가중치를 넣어 초기화를 해준다. ▼
모든 정점을 경유할 정점으로 설정하여 모든 정점을 탐색해본다.
1. 두 정점이 1번 정점을 경유할 때의 가중치를 구해본다
4번 -> 1번 -> 2번 : table[4][2]의 값은 INF지만, 새로운 값 9보다 크므로, 9로 교체해준다. ▼
2. 다음에는 두 정점이 2번 정점을 경유할 때의 가중치를 구해본다.
2번 정점을 경유하는 경우는 여러가지가 있으므로, 전부 확인해본다.
1번 -> 2번 -> 4번 : table[1][4]값이 INF로, 더 크므로 5로 교체해준다. ▼
3번 -> 2번 -> 3번 : table[3][3]값이 INF로, 더 크므로 3으로 교체해준다. ▼
3번 -> 2번 -> 4번 : table[3][4]값이 INF로, 더 크므로 2로 교체해준다. ▼
4번 -> 1번 -> 2번 -> 4번 : table[4][4]값이 INF로, 더 크므로 10으로 교체해준다. ▼
3. 다음에는 두 정점이 3번 정점을 경유할 때의 가중치를 구해본다.
3번 또한, 3번 정점을 경유하는 경우는 여러가지가 있으므로, 전부 확인해본다.
1번 -> 3번 -> 2번 : table[1][2]값이 4로 2보다 더 크므로 2로 교체해준다. ▼
1번 -> 3번 -> 2번 -> 4번 : table[1][4]값이 5로 3보다 더 크므로 3으로 교체해준다. ▼
2번 -> 3번 -> 2번 : table[2][2]값이 INF로 3보다 더 크므로 3으로 교체해준다. ▼
4번 -> 3번 -> 2번 : table[4][2]값이 9로 6보다 더 크므로 6으로 교체해준다. ▼
4번 -> 3번 -> 2번 -> 4번 : table[4][4]값이 10으로 7보다 더 크므로 7로 교체해준다. ▼
4. 다음에는 두 정점이 4번 정점을 경유할 때의 가중치를 구해본다.
4번 또한, 4번 정점을 경유하는 경우는 여러가지가 있으므로, 전부 확인해본다.
1번 -> 3번 -> 2번 -> 4번 -> 1번 : table[1][1]값이 INF로 7보다 더 크므로 7로 교체해준다. ▼
2번 -> 4번 -> 1번 : table[2][1]값이 INF로 6보다 더 크므로 6으로 교체해준다. ▼
3번 -> 2번 -> 4번 -> 1번 : table[3][1]값이 INF로 7보다 더 크므로 7로 교체해준다. ▼
5. 이렇게 4번 정점까지 다 확인했다면, 오른쪽의 행렬표가 i
정점과, j
정점간의 최단 거리가 된다. ▼
의사 코드
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u,v)
dist[u][v] ← w(u,v) // 변 (u,v)의 가중치
for each vertex v
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
시간 복잡도
정점의 개수 V만큼 반복문이 3중으로 수행되므로, O(V^3)의 시간 복잡도를 갖는다.
'Algorithm > Algorithm 개념' 카테고리의 다른 글
분리집합과 Union-Find (0) | 2024.02.17 |
---|---|
벨만 포드 (0) | 2024.02.15 |
다익스트라 (0) | 2024.02.13 |
MST, 최소 신장 트리 (0) | 2024.02.08 |
그래프와 그래프 탐색 (0) | 2024.02.07 |