[알고리즘] 플로이드-와샬(Floyd Whshall) 알고리즘

0. 개요

모든 정점에서 모든 정점으로의 최단 경로를 구할 수 있다.

단, 모든 정점은 양의 간선이여야 한다.

1. 구현 방법

우선 정점의 개수가 V개 라면 V X V 의 배열을 만들어야 한다.

배열의 [3][5] 이라면 3번 정점 -> 5번 정점의 최단 거리를 나타내는 것이다.

구현 방법은 다음과 같다.

이차원 배열은 다음과 같이 저장한다.

• 주어진 간선은 이차원배열에 저장
• 이차원 배열에서 X축과 Y축이 같으면 0으로 저장
• 간선에 나와 있지 않은 숫자들은 INF(무지막지하게 큰 수)로 저장

for 경유정점 in range(V):
	for 시작 정점 in range(V):
		for 도착정점 in range(V):
			dist[시작정점][도착종점] = min(dist[시작정점][도착종점], dist[시작종점][경유정점] + dist[경유정점][도착정점])

플로이드 와샬 알고리즘은 면밀히 살펴보면 다이나믹 프로그래밍을 이용하고 있음을 알 수 있다.

왜냐하면 계속 해서 1번 노드 부터 N번 노드까지의 최단 거리를 최신화 하고 최신화 한 데이터를 다른 곳에서 사용하기 때문이다.

2. 시간 복잡도

정점의 개수 V 만큼 총 3겹으로 반복하기에,

시간 복잡도는 O(V^3) 이다.