플로이드 워셜 알고리즘(Floyd Warshall)

플로이드 워셜 알고리즘

다이나믹 프로그래밍에 의거하는 알고리즘이다.

모든 노드 간의 최단거리를 구하는 것이 목적이므로, 2차원 인접 행렬을 구성한다.

플로이드 워셜 알고리즘 점화식

 

다익스트라 알고리즘과 차이

다익스트라 알고리즘

• 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 1차원 리스트 기반의 최단 거리 테이블 사용

플로이드 워셜 알고리즘

• 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘(거쳐가는 정점을 기준으로 최단 거리를 구함)
• 2차원 리스트 기반의 테이블 사용
• 그래프의 간선들 중 음의 가중치가 존재해도 실행할 수 있음

 

주요 코드

inf = int(1e9) #무한을 의미하는 값, 보통 10억으로 초기화함

graph = [[inf]*(n+1) for _ in range(n+1)] #n은 노드 개수


for k in range(1, v+1):
	for i in range(1, v+1): # i =출발지
    	for j in range(1, v+1): # j = 목적지
        	dp[i][j] = min(dp[i][j], dp[i][k] +dp[k][j])

i는 출발 노드이고 j는 도착 노드이다. 그리고 k는 거쳐가는 노드이다. 이들의 순서는 매우 중요하다.

돌면서 i에서 j로 바로 가는 것보다, k를 거쳐서 j로 가는 게 더 효율적일 경우에는 값을 갱신한다.

k는 가장 바깥쪽에 있는 선택지이므로, 여러 경유지를 선택하는 것도 포함된다.

 

초기값은 위와 같이 설정된다. k는 간선의 개수인데, 이게 바로 플로이드 워셜 알고리즘의 핵심이다.

위의 경우는 k가 0일 때, 즉 0개의 간선을 거쳐서 모든 노드에서 모든 노드로 가는 경우이다.

하지만 이 경우에는 자신 → 자신으로 가는 방법밖에 없고, 결국 0으로 초기화된다.

 

이후 k를 1 증가하면, 1개의 간선을 거쳐서 모든 노드에서 모든 노드로 가는 경우와 같다.

이런 식으로 k를 계속 늘려가면서 최소 거리 비용을 비교한다.

이 과정은 결과적으로 인접행렬(각 정점에서 정점까지의 거리 비용으로 구성되어 있음)과 같다.

 

시간복잡도

3중 for문으로 구성되어 있기 때문에 시간복잡도는 O(n^3)이다. 

 

플로이드 워셜 알고리즘을 이용한 문제

https://www.acmicpc.net/workbook/view/3581

문제집: 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) (daejjyu)

 

개념 잡기 위해서 추천하는 기본 문제 

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙