[동빈북] 플로이드 워셜 알고리즘

최단 경로를 구하는 알고리즘은 크게 3가지가 있다고 앞에 다익스트라 알고리즘 공부를 할 때 설명했다. 그 중에 플로이드 워셜 알고리즘에 대해서 알아보자.

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 무엇일까, 그리고 왜 사용할까? 다익스트라 알고리즘과는 무엇이 다를까?

다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는 경우' 에 사용하는 알고리즘이고, 그리디 알고리즘의 한 종류라고 볼 수 있다.

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 에 사용하는 알고리즘이고, 아래 그림처럼 단계를 반복하며 점화식에 맞게 리스트를 갱신하기 때문에 다이나믹 프로그래밍(Dynamic Programming)이라고 볼 수 있다.

밑에 그림에 있는 예시를 보면서 구체적으로 확인해 보도록 하자.

이렇게 점화식에 맞게 계속 테이블을 갱신해주면 된다. 그래서 다익스트라 알고리즘보다 훨씬 간단하지만, 시간 복잡도가 엄청나게 차이난다. 아마도 이 알고리즘을 사용하는 문제에서는 데이터의 개수나 시간을 엄청 여유있게 줄 것 같다.

구현 코드

이번엔 코드를 살펴보자.

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):
    graph[i][i] = 0

for _ in range(m):
    # A에서 B로 가는 비용은 C.
    a,b,c = map(int,input().split())
    graph[a][b] = c
    
# 점화식 그대로 구현.
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()

다익스트라 알고리즘보다 훨씬 간단하다. 정말 그냥 직관적으로 개념 따라서 사용하면 되는 알고리즘이다.