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

플로이드-와샬(Floyd-Warshall) 알고리즘

---

'거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 )

 

 

점화식

 

즉, (1) 정점 a에서 정점 b로 가는 최소 비용과 (2) 정점 a에서 정점 k로 가는 비용 + 정점 k에서 정점 b로 가는 비용을 비교하여

더 적은 비용을 가지는 쪽을 취하는 것이다.

 

N개의 노드가 있을 때, N번만큼의 단계를 반복하여 점화식에 따라 2차원 리스트를 갱신하기 때문에

동적 계획법(Dynamic Programming) 알고리즘에 속한다.

( ↔︎ 다익스트라 : 탐욕(그리디) 알고리즘 )

 

* 동적 계획법(Dynamic Programming, DP)

     하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장, 그 결과를 다시 큰 문제를 해결할 때 사용하는 것

* 탐욕 알고리즘(Greedy Algorithm)

     선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

 

과정

플로이드-와샬 알고리즘의 과정을 알아보기 위한 예시로, 아래의 그래프를 보자.

 

[ round 0 ]

각 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 나타내면 다음과 같다.

(INF : 무한, 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻)

 

	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	INF
3번	5	INF	0	4
4번	INF	INF	2	0

 

이 배열에는 현재까지 계산된 최소 비용이 저장될 것이다. (최단 거리 테이블)

 

[ round 1 ]

1번 정점을 거쳐가는 경우를 보며 해당 배열을 갱신해준다.

 

(1) 1번 정점에서 n번 정점으로 가는 비용

(2) 1번 정점에서 k번 정점으로 가는 비용 + k번 정점에서 n번 정점으로 가는 비용

→ 더 작은 비용으로 해당 배열 값을 변경

 

	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

 

* 붉은 부분 : 확인을 해야하는 부분

* 볼드 처리 : 최소 비용이 변경된 부분

 

[ round 2 ]

2번 정점을 거쳐가는 경우를 보며 해당 배열을 갱신해준다.

 

	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

 

[ round ~ ]

동일하게 3번, 4번, ... 정점을 거쳐가는 경우를 보며 해당 배열을 갱신한다.

 

위 예제에서의 최종 최단 거리 테이블은 아래와 같다.

 

	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

구현 (Python)

---

INF = int(1e9)  # infinite
dp = [[INF for _ in range(N)] for _ in range(N)]  # 최단 거리 테이블

for i in range(N):
    # 간선에 대한 정보를 최단 거리 테이블에 넣기

# 플로이드-와샬 알고리즘
for k in range(N):  # k : 거쳐가는 노드
    for i in range(N):  # i : 출발 노드
        for j in range(N):  # j : 도착 노드
            if dp[i][k] + dp[k][j] < dp[i][j]:
                dp[i][j] = dp[i][k] + dp[k][j]  # 갱신