플로이드 워셜 알고리즘
플로이드 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.
- 다익스트라 : 단계마다 최단 거리를 가지는 노드를 하나씩 반복적 선택 , 해당 노드를 거치는 경로를 확인하며 테이블을 갱신해 나간다. ( 탐욕법 )
- 플로이드 : 단계마다 ' 거쳐 가는 노드'를 기준으로 수행되지만 매번 방문하지 않는 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. ( 동적 프로그래밍 )
노드의 개수가 N개일 때, 알고리즘상 N번의 단계를 수행하고 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려한다. 따라서 총 시간 복잡도는 O(N^3)이다.
플로이드 알고리즘에서는 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담기 때문에 2차원 리스트를 할당하고 저장한다.
따라서 매 단계마다 2차원 리스트를 처리하므로 O(N^2)의 시간이 소요된다.
각 단계에서 해당 노드를 거쳐 가는 경우를 고려하고 해당 노드를 거쳐가는 경우가 빠른 경우 갱신한다.
즉 알고리즘에서는 현재 확인하고 있는 노드를 제외하고 N-1개의 노드 중 서로 다른 노드 (A, B)쌍을 선택하고 모두 계산한다.
따라서 (N-1) P 2개의 쌍을 반복해서 확인한다.
점화식 : D_ab = min( D_ab, D_ak + D+kb )
다음과 같은 그래프에서 시물레이션을 해보자 !
(step 0) 1차적으로 연결된 간선에 대해서만 테이블에 채워넣고 나머지는 무한으로 초기화
| 출발 \ 도착 | 1번 | 2번 | 3번 | 4번 |
| 1번 | 0 | 4 | 무한 | 6 |
| 2번 | 3 | 0 | 7 | 무한 |
| 3번 | 5 | 무한 | 0 | 4 |
| 4번 | 무한 | 무한 | 2 | 0 |
(step 1) 1번 노드를 거쳐가는 D_a1 + D_1b 에 대해 계산한다 3_P_2
단계에서 각 노드 A-> B로 가는 경우 1을 거치는 경우와 원래 테이블 값과 비교하여 갱신한다
표를 보면 1과 직접 연결되지 않은 노드의 간선에 대해 조사한 것이 6개임을 알 수 있다.
| 출발 \ 도착 | 1번 | 2번 | 3번 | 4번 |
| 1번 | 0 | 4 | 무한 | 9 |
| 2번 | 3 | 0 | 7 | 9 |
| 3번 | 5 | 9 | 0 | 4 |
| 4번 | 무한 | 무한 | 2 | 0 |
(step 2) 위와 같이 2번 노드에서도 적용한다
(step 3) 3번 노드에서도 적용
(step 4) 4번 노드에서도 적용한다.
(결과)
노드의 개수가 총 4개이므로 step4까지 알고리즘을 수행했다.
결과 테이블은 아래와 같고 내용은 모든 노드에서. 모든 노드로 가는 최단거리를 표현하고 있다. 시간복잡도는 O(N^3)이다.
| 출발 \ 도착 | 1번 | 2번 | 3번 | 4번 |
| 1번 | 0 | 4 | 무한 | 6 |
| 2번 | 3 | 0 | 7 | 9 |
| 3번 | 5 | 9 | 0 | 4 |
| 4번 | 7 | 11 | 2 | 0 |
플로이드 워셜 알고리즘 소스코드 .py
INF = int(1e9)
n = int(input())
m = int(input())
graph = [INF] * (n + 1) for _ in range(n+1)]
for a in range(1, n+1):
for b in range(1, n+1):
if a==b:
graph[a][b] = 0
for _ in range(m):
a,b,c = map(int, input().split())
graph[a][b] = c
for k in range(1, n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])