[그래프] 플로이드-워셜

플로이드-워셜

그래프에서 최단거리 구하는 알고리즘 3개(다익스트라, 벨만포드, 플로이드-워셜) 중 1개

기능	특징	시간복잡도(노드수 : V)
모든 노드 간(V³인 이유) 최단경로 탐색	음수 가중치 엣지가 있어도 수행 가능 (단, 음수사이클 x) 동적 계획법 원리를 이용해 알고리즘에 접근	O(V³) (V = 100 / 200 , 1000)

 

<핵심 이론>

(3중 for문으로 코드구성이 간단하기 때문에 쉽게 암기할 수 있음.)

 

A노드에서 B노드 까지 최단 경로를 구했다고 가정했을 때 최단경로 위에 K노드가 존재한다면 그것을 이루는 부분경로 역시 최단경로를 의미한다.

 

플로이드-워셜 점화식

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

K는 S부터 E까지 도달하는데 위치한 노드이다.

S부터 E까지 도달하는 데 위치한 K는 2개가 될 수도, 3개가 될 수도 있다.

최단경로 예	부분 최단 경로
↗ ⓚ ↘ ⓢ → ⓚ → ⓔ ↘ ⓚ ↗	ⓢ→ ⓚ	ⓚ → ⓔ

 

갈수 있는 모든 ⓚ를 대입하여 그중 가장 작은 `부분 최단경로 거리`의 합을 구한다.

---

 

Step 01) 리스트 선언하고 초기화하기

D[S][E]는 노드S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의한다.

S와 E값이 같은칸은 0, 다른 칸은 ∞로 초기화 한다

(S == E 조건은 자기 자신에게 가는데 걸리는 최단 경로값이 0을 의미하기 때문,
∞ 는 노드 S에서 노드 E까지 절대 갈수 없는 경로를 뜻한다. )

S\E	①	②	③	④	⑤
①	0	∞	∞	∞	∞
②	∞	0	∞	∞	∞
③	∞	∞	0	∞	∞
④	∞	∞	∞	0	∞
⑤	∞	∞	∞	∞	0

 

Step 02) 최단거리 리스트에 그래프 데이터 저장하기

출발노드는 S 도착노드는 E, 엣지의 가중치 W 라고 했을 때 D[S][E] = W 로 엣지의 정보를 리스트에 입력

이로써 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한다는 사실 알게됨

 

그래프				최단거리 리스트
8　   15     ① → ② → ⑤ 3 ↓   -4↓ 2↗↙5     ③ → ④ 　　 8				S\E	①	②	③	④	⑤
				①	0	8	3	∞	∞
				②	∞	0	∞	-4	15
				③	∞	∞	0	13	∞
				④	∞	∞	∞	0	2
				⑤	∞	∞	∞	5	0

ex) D[5][4] = 5

 

Step 03) 점화식으로 리스트 업데이트 하기

기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 리스트의 값을 업데이트 한다.

 

플로이드 워셜 알고리즘 로직

 

for (경유지 K에 관해) - (1~N)　← 제일 바깥 for문 = K ★암기★

　for (출발노드 S에 관해) - (1~N)

　　 for (도착노드 E에 관해) - (1~N)

　　　D[S][E] = Math.min(D[S][E], D[S][S] + D[K][E]) ←  점화식 적용 ★암기★

위 로직과 점화식에 의해 이전값과 비교해서 더 작은 경유지로 UPDATE된다.

 

최종 결과 리스트

S\E	①	②	③	④	⑤
①	0	8	3	4	6
②	∞	0	∞	-4	-2
③	∞	∞	0	13	15
④	∞	∞	∞	0	2
⑤	∞	∞	∞	5	0

(3중 for문으로 나오는 최종 최단거리 리스트(인접행렬))

완성된 리스트는 모든 노드 간의 최단거리를 알려준다.

 

ex) ① → ⑤의 최단거리 = D[1][5] = 6

---

∴모든 쌍에 대한 최단거리를 표현한다.

플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 확인해 주기 때문에 시간복잡도가 O(V³) 으로 빠르지 않은 편이다.

이에따라 플로에드-워셜 알고리즘을 사용해야 하는 문제가 나오면 일반적으로 노드 갯수의 범위가 드른 그래프에 비해 적게 나타나는 것을 알 수 있다.