플로이드의 모든 쌍 최단거리 알고리즘

[1. 개요]

다익스트라 알고리즘, 벨만포드 알고리즘은 한 개의 시작점에서 다른 모든 정점까지의 최단거리를 계산한다.

그래서 전체 N개의 정점 쌍 간의 최단거리를 구하기 위해서는 N 번의 다익스트라, 벨만포드 알고리즘을 사용해야 한다.

 

그러나 적절한 경우에 좀 더 간단하게 모든 정점 쌍 간의 최단 거리를 구할 수 있는데,

이 때 사용하는 알고리즘이 플로이드-워셜 알고리즘 이다.

---

[2. 원리]

경로의 경유점

• 두 정점 u 와 v 를 잇는 어떤 경로가 있다.
• 이 경로는 항상 시작점, 끝점이 u, v 이며 이는 자명하다.
• u 와 v 를 직접 연결하는 경로 일 수 있으나, 다른 정점을 거쳐서 u 와 v 를 이을 수 있다.
• 이 때, 사용되는 정점을 경유점이라 한다.

u 와 v 가 직접 연결 된 경로보다 경유점을 거치는 경로가 더 짧을 수 있다. 

 

이렇게 정점 집합 s 에 포함 된 정점 만을 경유점 'x' 로 사용한다면,  아래와 같은 경우를 생각해볼 수 있다.

1. 경로가 x 를 경유하지 않는다.
   => 이 경로는 S - {x} 에 포함된 정점들만을 경유점으로 사용한다.
2. 경로가 x 를 경유한다.
   => u ~ v 경로는 u ~x 와 x ~ v 이렇게 두 개의 경로로 나눌 수 있다.

정점 집합 S 에 정점을 하나씩 추가해가면서 최단 경로를 구해나간다.

=> 반복적 동적 계획법

 

구현부에서 

가장 바깥쪽 for 문 이 바로 경유점에 사용할 정점 집합 S 에 해당

2번째 for 문이 u 에 해당

3번째 for 문이 v 에 해당한다.

---

[4. 경로 복원]

플로이드 알고리즘은 최단 경로에 간선을 하나씩 추가해가는

다익스트라나 벨만포드 알고리즘과 다른 방식으로 동작하므로, 

실제 경로를 계산하는 과정도 다르다.

 

과정

1. 플로이드 알고리즘을 수행하면서, u-v 최단 경로가 갱신되었을 때 사용한 경유점을 저장한다.
2. 플로이드 알고리즘 종료 후, u ~ v 최단거리가 존재하지 않는다면 경로를 구할 수 없다.
3. u ~ v 최단경로가 존재한다면, u ~ v 경로가 경유점 x 를 거쳐가야 한다.
4. u ~ x 의 최단 경로를 구한다.
5. x ~ v 의 최단 경로를 구한다.
6. 4 와 5 에서 구한 최단 경로를 합친다.
   => x 가 중복되니, 한쪽 경로에서는 제거되어야 한다.
   => 3 ~ 6 은 재귀적으로 처리되어야 한다.

---

[5. 예제]

https://testkernelv2.tistory.com/448