[알고리즘 이론] 최단 경로 알고리즘(2) - 플로이드 워셜 알고리즘

최단 경로 문제

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.

 

최단 경로 문제의 상황은 다음과 같이 다양하다.

• 한 지점에서 다른 한 지점까지의 최단 경로
• 한 지점에서 다른 모든 지점까지의 최단 경로
• 모든 지점에서 다른 모든 지점까지의 최단 경로

 

최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 더 많이 출제된다. 따라서 포스팅에서도 최단 경로가 아닌 최단 거리를 출력하는 코드를 구현할 것이다.

 

컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 이렇게 3가지이다. 오늘은 이 중 플로이드 워셜 알고리즘에 대해 알아보자. 

 

※ 이전 포스팅 다익스트라 최단 경로 알고리즘의 연장입니다.

---

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

다익스트라 알고리즘이 '한 노드'에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘이었다. 반면 플로이드 워셜 알고리즘은 '모든 노드'에서 다른 모든 노드까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘이다.

 

플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다는 점이 다르다. 또한 플로이드 워셜 알고리즘은 모든 노드에 대한 최단 거리 정보를 저장해야 하므로 2차원 리스트를 이용한다.

 

플로이드 워셜 알고리즘은 다이나믹 프로그래밍으로 분류된다. 노드의 개수가 N이라고 할 때, N번만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹프로그래밍으로 볼 수 있다. 

 

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인하여 a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사하여 최단 거리 테이블을 갱신한다. 따라서 점화식은 D(a,b) = min(D(a,b), D(a,k)+D(k,b)) 이고 동작 과정은 다음과 같다.

 

1. 최단거리 테이블을 초기화한다. (인접한 노드라면 그 거리, 아니라면 '무한'으로 초기화)

   

2. 1번 노드를 거쳐 가는 경우를 고려하여 최단 거리 테이블을 갱신한다.

   

3.  나머지 노드에 대해서도 반복한다.

   

---

플로이드 워셜 알고리즘 구현

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split())    # 노드의 개수, 간선의 개수 입력
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 2차원 리스트(그래프 표현)를 만들고, 무한으로 초기화

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

for _ in range(m): # 간선 정보 입력
    a, b, c = map(int, input().split())     # a번 노드에서 b번 노드로 가는 비용 c
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
# 점화식: Dab = min(Dab, Dak + Dkb)
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("INFINITY", end = " ")
        else:
            print(graph[a][b], end = " ")
    print()

위 코드를 보면 3중 반복문을 통해 점화식을 구현하고 있다. 노드의 개수가 N개 일 때 N번의 단계를 수행하며 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려하기 때문에 플로이드 워셜 알고리즘의 시간 복잡도는 O(N^3)이다. 따라서 노드의 개수가 약 500개 이하일 때만 사용을 고려해야 한다.

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)