10주차 플로이드 워샬
모든 최단 경로를 구하는 알고리즘
다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.
플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.
다익스트라 알고리즘이 출발노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 리스트를 이용한 반면, 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 다르게 2차원 리스트에 최단거리 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문
다익스트라 : Greedy(그리디)
플로이드-워셜 : DP(다이나믹 프로그래밍)
- 점화식(So EASY!)
‘A에서 B로 가는 최소 비용'과 ‘A에서 K를 거쳐 B로 가는 비용'을 비교하여, 더 작은 값으로 갱신하겠다
D_ab = min(D_ab, D_ak + D_kb)
<step 1>
1번 노드(K=1)를 거쳐가는 경우를 고려한다. 6(3P2)가지 경우에 대해서 고려하면 된다.
D23 = min(D23, D21+D13)
D24 = min(D24, D21+D14)
D32 = min(D32, D31+D12)
D34 = min(D34, D31+D14)
D42 = min(D42, D41+D14)
D43 = min(D43, D41+D13)
<step 2>
2번 노드(K=2)를 거쳐가는 경우를 계산한다. 2번 노드를 제외한 1, 3, 4번 노드에서 2개의 노드를 뽑는 경우를 고려한다.
(1, 3), (1, 4), (3, 1), (3, 4), (4, 1), (4, 3) 6가지에 대해 값을 갱신한다.
<step 3>
3번 노드도 마찬가지로 (1, 2), (1, 4), (2, 1), (2, 4), (4, 1), (4, 2) 6가지를 고려해 이 과정을 반복하면 다음과 같은 결과가 나온다.
<step 4>
4번 노드 역시 (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)를 고려해 값을 갱신한 결과는 다음과 같다.
<
노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)
플로이드 워셜이 더 낫다(안전하다)
| 최선 | 평균 | 최악 | |
|---|---|---|---|
| 다익스트라 | O(V^2 log V) | O(V^3 log V) | O(V^3 log V) |
| 플로이드워셜 | O(V^3) | O(V^3) | O(V^3) |
다익스트라 O(E log V) → 모든 정점에 대해서 계산 → O(VE log V)
E는 트리의 경우에 E=V로 해석해도 된다. 하지만 완전 연결 그래프에 가까우면 E=V^2로 해석해야 한다.
즉 최악의 경우 O(VE logV)는 O(V^3 log V) 가 된다.
-
플로이드 워셜
정점의 개수가 작을 때에는 적합하지 않지만, 간선의 개수가 많은 경우에도 효율적으로 동작합니다.
-
다익스트라
간선의 개수가 적을 때에는 효율적이지만, 간선의 개수가 많은 경우에는 더 비효율적 입니다.
- 2차원 리스트 생성해 모든 값을 무한으로 초기화
- 자기 자신에서 자기 자신으로 가는 비용 0으로 초기화
- 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
- 점화식에 따라 플로이드 워셜 알고리즘을 수행
- 수행된 결과 출력
https://wooono.tistory.com/526
https://www.youtube.com/watch?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&v=acqm9mM1P6o&feature=youtu.be