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

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

 

다익스트라 알고리즘은 특정 시작점이 있을 때만 사용할 수 있다. 따라서 모든 지점의 거리를 구하는 데는 번거로울 수 있다(모든 점들에 대해 다익스트라 알고리즘을 수행해야 한다). 이 때 사용하는 것이 플로이드-워셜 알고리즘이다.

 

기본 아이디어는 다익스트라와 유사하다. 단, 이를 모든 노드가 시작점일 때를 고려하여 수행할 뿐이다. A에서 B로 가는 경로보다 A에서 X를 거쳐 B로 가는 경로가 짧다면 최단 경로를 갱신하는 방식이다. 그러나 애초에 모든 점을 방문해야 하므로 다익스트라 알고리즘에 비해 느리다. 따라서 지점의 갯수가 적다면 다익스트라를 여러 번 돌리는 게 나을 수 있다. 코드를 보며 알아보자.

 

2. 구현

n = int(input())
graph = []
dist = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    graph.append(input().split())
for i in range(n):
    for j in range(n):
        graph[i][j] = int(graph[i][j])
        if graph[i][j] != 0:
            dist[i][j] = graph[i][j]
        elif i == j:
            dist[i][j] = 0
        else:
            dist[i][j] = float('inf')

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]


for i in range(n):
    print(dist[i])

여기서 중요한 것은 k를 포문의 가장 바깥에 두는 것이다. dist[i][j]는 연결될 수 있는 모든 k에 대해서 최적을 구한 뒤 갱신되어야 한다. 그러나 이것이 가장 안으로 들어온다면 처음 k번만 고려된다. 만약 그래프가 한 번 갱신된 이후라면, k가 가장 안쪽에 있을 때는 갱신된 값에 대한 최적의 값을 쓸 수 없다.