[Algorithm] 플로이드 워셜

플로이드 워셜 알고리즘이란?

플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다.

즉, 다익스트라 알고리즘과 다르게 출발점이 정해져있지 않다는 것이다.

플로이드 워셜 알고리즘의 핵심은 위의 점화식을 구현하는데 있다.

$D_{ab}$는 a노드에서 b노드까지 가는데 소요되는 비용을 의미한다.

여기서 a노드에서 b노드를 가는데 중간에 k노드를 거쳐서 간다고 생각해보자

기존에 $D_{ab}$ 보다 $D_{ak}+D_{kb}$(k노드를 경유)의 값이 더 작은 경우가 있을 것이다.

우리는 최단거리를 찾는 것이므로 $D_{ab}$의 값을 $D_{ak}+D_{kb}$로 갱신해준다.

이것을 모든 노드에 대하여 반복한다면 결국에는 모든 노드에서 다른 모든 노드로 가는 최단경로를 구할 수 있다.

INF = int(1e9)

n,m = map(int,input().split())

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

# 간선 정보를 2차원 행렬에 반영
for _ in range(m):
    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 i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j] == INF:
            print('INF', end = '  ')
        else:
            print(graph[i][j], end = '  ')
    print()

위에 코드에서 보다시피 인접 행렬을 기반으로 하며, 3중 for문을 이용해서 구현한다.

1. 첫 번째 for문은 거쳐가는 노드를 기준으로 한다.
2. 두 번째 for문은 출발하는 노드를 기준으로 한다.
3. 세 번째 for문은 도착하는 노드를 기준으로 한다.
4. graph[a][b], graph[a][k]+graph[k][b]를 비교해 더 작은 값으로 갱신한다.

시간 복잡도

알고리즘의 시간 복잡도는 O($N^{3}$)이다.

N개의 노드가 있을 때 거쳐가는 노드 하나당 O($N^{2}$) 연산을 시행하기 때문이다.

특징

• 다익스트라 알고리즘과 달리 음의 간선이 있어도 정상 수행(하지만 음수 사이클이 있으면 안됨)
• 다이나믹 프로그래밍 기법을 사용한다.