[Python] 모든 지점에서의 최단경로를 찾는 플로이드 워셜(Floyd-Warshall) 알고리즘

🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다.

 

이번 포스팅에서는 또 다른 최단 경로 알고리즘인 플로이드 워셜 알고리즘에 대해 알아보려고 한다. 저번 포스팅에서 배운 다익스트라(Dijkstra) 알고리즘은 특정 노드라는 시작 노드 1개를 지정하고 그 시작 노드에서 다른 노드들 까지의 최단거리를 구하는 방법이었다. 하지만 플로이드 워셜 알고리즘은 시작 노드를 1개로 설정하는 것이 아닌 다수 즉, 모든 노드에서 모든 노드까지의 최단거리를 구하는 방법이다.

 

다익스트라 알고리즘은 하나의 특정 노드에서 다른 노드까지가는 최단 거리를 구하는 것이었다.

---

다익스트라 알고리즘의 구현 동작을 다시 회고해보면 다익스트라 알고리즘은 단계마다 탐색하는 노드 즉, 거쳐가는 노드를 기준으로 알고리즘을 수행했었다. 플로이드 워셜 알고리즘도 이와 마찬가지이다. 그런데 약간의 차이점이 있다. 바로 매번 단계를 수행할 때마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾을 필요가 없다는 것이다. 왜냐하면 플로이드 워셜은 시작노드가 여러개이기 때문이다. 따라서 매 단계마다 $O(N^2)$의 연산을 수행하므로 노드의 총 개수인 $N$개임을 감안하면 총 시간 복잡도는 $O(N^3)$이 되게 된다. 

 

또 한 가지 중요한 차이점이 있다. 다익스트라 알고리즘은 시작노드가 1개이기 때문에 거리 테이블을 1차원 리스트로 정의했었다. 하지만 플로이드 워셜은 모든 노드에서 모든 노드간의 최단거리를 구하는 것이므로 N by N 사이즈의 2차원 리스트를 정의해야 한다. 그리고 각 행을 시작, 열을 도착으로 간주한다. 예를 들어, (1, 2) 라고 한다면 1번 노드에서 2번 노드까지의 거리를 의미하며 (1, 2)의 값을 거리 값으로 간주한다. 

 

또한 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 알고리즘이 녹아들어 있다. 저번에 배운 다익스트라 알고리즘은 그리디 알고리즘을 사용했다. 플로이드 워셜 알고리즘은 최단거리를 갱신할 때 점화식을 사용한다는 점에서 다이나믹 프로그래밍이 적용되어 있다고 할 수 있다. 점화식은 다음과 같이 나타낸다. $$D_{ab} = \min{\left(D_{ab}, D_{ak} + D_{kb} \right)}$$

위 점화식을 해석하자면 $a$ 노드에서 $b$ 노드까지의 거리는 $a$에서 $b$로 가는 거리와 $a$에서 $k$로 가는 거리, $b$에서 $k$로 가는 거리의 합 중 최솟값으로 갱신하라는 의미이다. 즉, $a$에서 $b$로 가는 거리를 $k$라는 탐색하고 있는 노드를 거쳐서 가는 거리 비용이 더 작으면 갱신하라는 것이다.

 

자, 그렇다면 플로이드 워셜 알고리즘의 동작과정을 살펴보기 위해 도식화해서 살펴보자.

1. 첫 번째 초기 단계

다음과 같이 노드와 간선이 주어져 있다고 가정하자. 그리고 이를 기반으로 오른쪽의 2차원 리스트 형태의 거리 테이블을 갱신시키자.

 

초기단계

2. 두 번째 단계

이제 순차적으로 1번 노드부터 4번 노드까지 일일이 확인하면서 거리 테이블을 갱신시킨다. 하나의 노드 당 탐색할 경우의 수는 6가지이다. 예를 들어, 1번 노드를 탐색하는 중이라면 2,3,4번 노드들 중 두 쌍의 순열을 생각해보면 (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3) 총 6가지가 된다. 그럼 한 예시로 위 거리테이블에서 (2, 3) 즉, 2번에서 3번으로 가는 최단 거리를 갱신시켜보자. 현재 2번에서 3번으로 가는 거리는 7이다. 그러면 탐색하는 노드 1번을 거쳐서 즉, 2번 -> 1번 -> 3번 노드로 가는 거리의 값은 3 + 무한 이다. 그러므로 이 중 최솟값인 거리 7을 유지한다. 점화식으로 나타내면 다음과 같다. $$D_{23} = \min{\left(D_{23}, D_{21} + D_{13} \right)}$$

 

위와 같은 방식으로 나머지 5가지의 경우 (2, 4), (3, 2), (3, 4), (4, 2), (4, 3)에 대해 모두 수행해보면 아래와 같이 거리 테이블이 갱신된다. 아래 테이블의 주황색 부분이 업데이트된 6가지 경우이다.

 

두 번째 단계

 

이제는 위와 같은 방식으로 2번, 3번, 4번 노드에 대해 동일하게 수행해주면 된다.

3. Python으로 플로이드 워셜 알고리즘 구현하기

그렇다면 이제 Python으로 해당 알고리즘을 구현해보자. 소스코드는 비교적 간단하다. 3중 반복문을 이용하되 점화식을 넣어주기만 하면 된다.

 

import sys

INF = int(1e9)
n = int(input())
m = int(input())
# 2차원 거리테이블 리스트 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자신의 노드간의 거리는 0으로 변경
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0
# 주어지는 그래프 정보 입력
for _ in range(m):
    # a -> b로 가는 비용은 c
    a, b, c = map(int, input().split())
    graph[a][b] = c

# k=거쳐가는 노드
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            print('도달할 수 없음', end=' ')
        else:
            print(graph[i][j], end=' ')
    print()