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

1. 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

모든 최단 경로를 구하는 알고리즘
다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.

 

2. 동작방식

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

각 경로의 중간 노드를 선택하여, 거리를 더 짧게 줄이는 과정을 반복한다.

초기 그래프를 인접형렬로 나타내면 아래와 같다.

INF는 해당 노드에서 특정노드까지 가는 길이 없음을 의미한다.

 

시작/끝	0	1	2	3
0	0	5	INF	1
1	INF	0	7	2
2	3	INF	0	INF
3	INF	INF	6	0

 

1) 1번 노드를 중간 노드로 설정할 경우

① 값이 변경될 경우

 

dist[0][2] = min(dist[0][2], dist[0][1] + dist[1][2]) = min(INF, 5 + 7 = 12) = 12

 

② 값이 변경되지 않을 경우

 

dist[0][3] = min(dist[0][3], dist[0][1] + dist[1][3]) = min(1, 5 + 2 = 7) = 1

시작/끝	0	1	2	3
0	0	5	✔ 12	1
1	INF	0	7	2
2	3	INF	0	INF
3	INF	INF	6	0

 

2) 2번 노드를 중간 노드로 설정할 경우

dist[1][0] = dist[1][2] + dist[2][0] = 7 + 3 = 10

dist[3][0] = dist[3][2] + dist[2][0]  = 6 + 3 = 9

시작/끝	0	1	2	3
0	0	5	12	1
1	✔ 10	0	7	2
2	3	INF	0	INF
3	✔ 9	INF	6	0

이런식으로 0번노드, 3번노드가 중간값일때도 계속해서 업데이트해준다.

 

 

 

최종 값들은 아래와 같다. (변경된 값들은 주황색으로 표시)

시작/끝	0	1	2	3
0	0	5	7	1
1	10	0	7	2
2	3	8	0	4
3	9	14	6	0

 

3. 시간 복잡도

이 알고리즘은 3중 for문으로 수행되기 때문에 시간복잡도는 O(|V|^3)이다.

 

모든 정점 쌍의 최단 거리를 구하기 때문에, 다익스트라 알고리즘은 O(|V| |E| log |V) 이므로, 다익스트라가 약간 더 빠르다.

벨만-포드의 경우에는 O(|V|^2 |E|)이고, 보통 정점의 수보다 간선의 수가 더 많기 때문에 플로이드-워셜이 조금 더 빠르다고 볼 수 있다.

4. 파이썬 구현 코드

m은 중간 노드

E는 노드의 개수이다.

 

 for문에는 i, j를 통해 각 노드별 모든 거리를 살펴보면서 k를 중간 노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 변경해준다.

# dist[i][i]에는 0이, 경로가 없는 값에는 INF가 있다는 가정하에

for m in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j], dist[i][m]+dist[m][j])

 

 

📖 reference

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

[그래프] 플로이드-워셜 알고리즘(Floyd-Warshall Alogrithm)