플로이드 워셜 알고리즘

0. 플로이드 워셜 알고리즘이란?

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용

- 매 단계마다 현재 노드를 거쳐 가는 노드를 기준으로 알고리즘을 수행

- DP - 최단 거리 정보 저장

 

1. 알고리즘 진행과정

0️⃣ 초기 거리 테이블 설정
     - 연결되지 않은 간선에는 무한대
     - 자기 자신은 0
     - 이외 간선들은 주어지는 거리
1️⃣ N번 돌면서 현재 노드 선택 >> 현재 노드를 거쳐서 지나가는 모든 경우를 고려
2️⃣ N^2번 돌면서 현재 노드를 거쳐 가는 모든 경로 순회
3️⃣ 원래 기록된 거리보다 현재 노드를 거쳐서 지나가는 거리가 더 짧다면 갱신
(직접 연결된 간선은 업데이트 X)

-> O(N^3)의 시간복잡도를 가진다

 

2. 점화식

D[i][j] = min(D[i][j], D[i][k] + D[k][j]) (1 <= k <= V)

i에서 j로 가는 이미 저장된 거리 와 i에서 k를 거쳐 j로 가는 거리 중 작은 것을 배열에 넣는다

 

3. 코드

for k in range(V):
	for i in range(V):
		for j in range(V):
			D[i][j] = min(D[i][j], D[i][k] + D[k][j])