[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm)

---

[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm)

---

 

 

 

플로이드 워셜 알고리즘은 edge에서 edge로 이동할 때 최소비용을 구하는 알고리즘이다.

모든 경로의 최소비용을 구할 수 있다.

 

---

구현

 

 

플로이드 워셜 알고리즘의 구현은 간단하다.

k, i, j를 사용하는 3중 for문이 있을 때

3중 for문으로 가장 바깥 k를 사용하는 for문은 edge의 총개수만큼 반복한다.

 

k는 중간에 거쳐가는 edge이다.

i는 시작 edge, j는 도착 egde로 사용한다.

 

현재 비용보다 거쳐가는 비용이 더 적다면 거쳐가는 비용을 사용한다.

 

자기 자신으로 가는 경로는 0, 도착이 불가능한 경로는 INF(충분히 큰 값)로 표시한다.

 

---

이해

 

구현은 간단하지만 이해는 쉽지 않았다.

플로이드 워셜 알고리즘은 가장 바깥 for문

즉, 거쳐가는 k가 계속 증가한다고 생각하면 된다.

(경로 값이 크다면 증가하지 않겠지만, 이해를 위해 증가한다고 생각)

 

[거쳐가는 edge]

 

 시작 -> 0 -> 도착

시작 -> 0->1 -> 도착

시작 -> 0->1->2 -> 도착

시작 ->  0->1->2->3... -> N개의 edge까지 -> 도착

 

단순히 거쳐가는 경우가 증가하게끔 나타냈지만

 모든 순열의 경로를 알 수 있다.

 

시작 -> 0->1 -> 도착

시작 -> 1->0 -> 도착

시작 -> 2->4->1 -> 도착

시작 -> 1->4->2->3->5 -> 도착

...

 

---

다른예제

 

k는 0번 edge부터 가장 마지막 edge까지  증가하며

i 부터 j까지 가는 모든 경우를 계속 갱신한다.

 

예를 들어

가장 처음 0번을 거쳐가는 경우를 생각하자. (k= 0)

0번을 거치며 2번 edge에서 4번 edge의 경로는 갱신되어

2번 (시작)  ->  0번 (거쳐감)  ->  4번 (도착)

2번 -> 4번 는 현재까지의 최소비용으로 갱신되었다.

 

(k=1)인 경우는 잠시 제쳐두고

그다음 2번을 거쳐가는 경우를 생각하자. (k=2)

그럼 2번을 거쳐가는 경우에서

1번 (시작) -> 2번 (거쳐감) -> 4번 (도착)

을 갱신하려 할 때

 

보기에는 단순히 2번을 거쳐가는 것으로 보이지만 사실

2번 -> 4번은

2번 -> 0번 -> 4번 을 사용한다. 이게 현재까지의 최소비용이었기 때문이다.

 

dist[2][4]는 2->0->4로 update되어있다.

1번 -----------> 2번 ------(0번을 지나는 경로)------> 4번

 

                                            

 

---

 

결국, 앞에서 구한 최소 경로를 반복적으로 사용하기 때문에

보기완 달리 사실 많은 edge들을 이동하는 경로의 최소 비용을 사용하는 것이다.

 

---