모든 정점에 대하여 다른 정점으로 가는 최단 거리(최소 가중치 합)을 구하는 방법 (표를 이용해 구현)
- 벨만포드 알고리즘을 각 정점에 대하여 실행시키면된다.
- 음수 가중치가 없다면 다익스트라 알고리즘을 실행할 수 있다.
- O(V^2 * E) → 그래프가 밀집되어 있으면 E = Θ(V^2)
- 다익스트라 binary heap 이용 → O(VElgV), 피보나치힙 이용 → O(EV + V^2lgV)
- 특수한 데이터 구조 외에 모든 케이스에 대하여 **O(V^3)**안에서 다룰 것이다.
전체 n개의 정점이 있다고 가정하면 shortest path distance (u,v)를 n*n 행렬로 표현할 것이다.
- 가중치는 i와 j의 조건에 따라 다르게 설정된다.
- W도 행렬로 표현 → 이를 이용해 동적프로그래밍처럼 표를 이용해서 문제를 해결한다!
- path p는 i → j의 최소 엣지를 m개 갖는 최단 거리라고 하자
-
p’는 i ~> k → j 즉 m-1개의 엣지를 갖는 경로이다.
p’도 최단거리여야 한다.(최적의 솔루션은 하위 솔루션도 최적!)
-
- Lij(m)은 최소 m개의 엣지를 포함하는 i ~> j 의 최단 경로의 최소 가중치 합을 의미한다.
-
기존의 경로 vs 경유하는 경로 1 추가했을때 둘중 최솟값으로!
-
최단 경로 계산
- m = 1 즉, 엣지를 1개만 사용하는 경우 Lij(m) = W행렬과 같다.
- 이것을 이용하여 m=1, 2, 3, … n-1까지 L(m) = Lij(m)을 구한다.
- L(n-1)은 최댓값 즉, 모든 정점에서 다른 정점으로 이동할 때의 최솟값을 담은 행렬이다.
- 만약 그래프가 음수 가중치 사이클이 없다면 최대 n-1엣지까지 포함하면 된다.
- 음수없으면 n-1을 넘어서 n, n +1 반복해도 똑같기 떄문에
- 더하는 과정 그림으로 설명
-
Pseudocode
- 시간 복잡도는 Θ(n^3)
- L(1) ~ L(n-1)까지의 테이블을 만드는 과정
- Θ(n^3) * Θ(n) ⇒ Θ(n^4)
- 실제 예시 (행이 출발지점, 열이 도착지점)
- L1 = W이고, L2는 2개의 엣지를 거쳐서 도착하는 것이므로, 1→5를 채울때 1→2→5,1→3→5,1→4→5를 확인해서 표를 갱신
- 향상시켜보자!
- L(m) (m ≥ n-1)의 행렬을 더이상 계산하지 않아도됨 (음수사이클 없을떄!)
- W^2 = 2개의 엣지를 이용할 때 최단 경로 비용을 행렬 곱으로 나타낸 것 (행렬 곱은 여기서는 EXTEND-SHORTEST-PATHS함수로 들어가면 실제론 두 행렬의 값을 더하는 것이 됌 ⇒ 1 → 5 → 3 이런 경로를 계산 해줄 수 있음)
- 이를 이용하면 n^3lgn까지 줄일 수 있다!
The Floyd-Warshall algorithm 플로이드 워셜 알고리즘
- 음수 가중치는 ok, 음수 가중치 사이클은 No!
- path p가 있다면 p를 구성하는 정점 중에 source, sink를 제외한 즉, 거쳐가는(intermediate) 집합 S을 찾아냄
- 예시 p <1,2,4,5> ⇒ {2,4}
- i → j까지의 최단 거리에서 {1,2,3,…,k} 중에서 거치는 모든 정점을 선택했을 때 최소 가중치 합이 dij(k)를 의미한다.
- k는 정점의 수와 같고 index가 k보다 클 수 없다.
- k가 만약 경유정점(intermediate)이 아니라면 P : i → j의 경유정점으로는 1,2,…,k-1 중에 선택될 것이다.
- k가 만약 경유정점이라면 P를 구성하는 p1, p2로 나눴을 때 p1, p2의 경유정점으로 k가 선택될 수 없다(경유정점으로 2번 선택되었다는 것은 사이클이 존재한다는 것)
- p1, p2의 경유정점은 1,2,…,k-1 중에 선택될 것이다.
-
dij(k)에서 k의 의미는 1~k까지 정점을 경유할 수 있을 때 가중치의 최소합을 의미한다.
- k = 0이면 경유할 수 있는 것이 없기에 Wij가 된다.
- k ≥ 1이면
- k가 경유정점이 되지 않으면 dij(k) = dij(k-1)
- k가 경유정점이 된다면 dij(k) = dik(k-1) + dkj(k-1)
- 이 둘 중 minimum 선택!
-
플로이드 워셜 pseudocode
-
최단 경로를 구축하는 과정
- πij(k)는 1,2,3,…,k 중에 거치는 정점으로 하여금 i → j의 경로의 j 정점 바로 이전 정점을 의미한다.
- πij(k)
- D(1)~D(n)까지 해주면 모든 경로에 대해 최소의 가중치 합을 찾을 수 있음!
- SLOW-ALL-PAIRS-SHORTEST PATHS(W)
- 플로이드워셜 알고리즘