플로이드 와샬

개요

---

플로이드-와샬 알고리즘은 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.

가중치가 음인 그래프는 있지만, 음수 싸이클은 없다.

(음수 싸이클이란? 음의 가중치가 더 커서 최단 경로를 계속해서 줄일 수 있는 상태의 간선을 말함.)

벨만-포드와 음의 가중치의 최단 경로를 계산할 수 있다는 점에서 비슷하지만, 플로이드-와샬 알고리즘은 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다.

 

즉, 벨만-포드와 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구했다면, 플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구한다.

또한 플로이드-와샬 알고리즘은 다이나믹 프로그래밍으로 볼 수도 있다.

 

 

알고리즘

---

알고리즘 분류와 특징

개요에서 이야기했듯, 플로이드-와샬은 다익스트라 알고리즘과 같이 다이나믹 프로그래밍의 한 종류로도 볼 수 있다.

특징으로는, 플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 최단 거리를 구한다는 것이다.

경유지를 기준으로 최단 거리를 구한다고도 할 수 있다.

 

알고리즘 동작

i행과 j열의 원소인 (i, j)원소는 정점 i로 부터 정점 j까지의 최단 경로를 의미한다.

1. 정점 i에서 정점 n 을 거쳐서 정점j 로 갈 때, n 을 거쳐 가는 것이 더 최단 경로일 경우 값을 갱신해준다.
2. 거쳐갈 모든 정점에 대해서 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)의 시간 복잡도를 갖는다.