[알고리즘] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘은

그래프에서 가능한 모든 노드 쌍에 대해

최단 거리를 구하는 알고리즘입니다


시간복잡도는 $O(V^3)$으로

다익스트라 알고리즘과는 달리,

모든 쌍에 대해 최단 거리를 구하고

음의 가중치를 가지는 그래프에서도 사용 가능한 것이 특징입니다


구현 난이도는

다익스트라 알고리즘에 비해 쉬운 편이지만

시간복잡도로 인해 노드 및 간선의 개수가 많은 경우에는

일반적으로 다익스트라 알고리즘을 사용해야 해결할 수 있는 경우가 많습니다

---

플로이드-워셜 알고리즘은

임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해

s와 e 사이의 노드인 m에 대해

s에서 m까지 가는데 걸리는 최단거리와

m에서 e까지 가는데 걸리는 최단거리를 이용합니다


조금 더 구체적으로 설명하자면,

임의의 노드 s부터 e까지 가는데 걸리는 최단거리를 d[s][e]라고 하겠습니다

이 d[s][e]를 구하기 위해서

s와 e 사이의 모든 노드 m에 대해

현재 d[s][e]에 저장되어 있는 값과

d[s][m] + d[m][e]의 값을 비교합니다

둘 중 더 작은 값을 사용합니다

이를 간단히 점화식으로 표현하면

$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

---

예시 코드

...

graph = [ [INF for _ in range(n+1)] for _ in range(n+1)]

...

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])

...

참고자료

[이것이 코딩 테스트다 with Python] 플로이드 워셜 알고리즘