[기술면접/알고리즘] 플로이드-워셜(Floyd-Warshall)

플로이드-워셜(Floyd-Warshall)에 대해 설명하세요

Keyword

모든 노드 간의, 음의 간선, 인접 행렬, 중간 노드

Script

모든 노드 간의 최단거리를 구하는 문제가 있을 때, 플로이드-워셜 알고리즘을 사용합니다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 (Single Source Shortest Path) 알고리즘이었다면, 플로이드-워셜 알고리즘은 모든 노드 간의 최단경로를 구할 수 있고 음의 간선도 사용할 수 있습니다.

이 알고리즘의 원리를 말씀드리자면, 먼저 모든 노드 간의 최단거리를 저장하기 위한 2차원 인접 행렬을 구성하고 현재 존재하는 간선에 대한 정보를 저장합니다. 그리고 나머지는 무한대로 초기화합니다.

이후 과정은 간단합니다. 모든 노드에 대해서 각각을 중간 노드로 설정한 후에 해당 노드를 중간 노드로 하여 다른 노드로 이동하는 경로의 길이를 구하여 최솟값을 최단거리 2차원 배열에 저장하는 과정을 반복합니다.

이렇게 모든 노드 사이의 최단 거리를 구할 수 있게 됩니다. 이때, 모든 노드 사이의 간선을 조회하기 때문에 O(n^2)의 시간복잡도를 가지고 이 과정을 모든 노드를 중간 노드로 두고 수행하기 때문에 총 O(n^3)의 시간복잡도로 알고리즘이 수행됩니다.

Additional

코드 (python)

from sys import stdin
from math import inf

n = int(stdin.readline())
m = int(stdin.readline())

# 이동 최소비용을 저장할 2차원 배열
cost = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, stdin.readline().split())
    cost[a-1][b-1] = min(cost[a-1][b-1], c)

# 플로이드 와샬 알고리즘 적용
k in range(n):
    cost[k][k] = 0
    for i in range(n):
        for j in range(n):
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

# 결과 출력
for row in cost:
    for i in range(n):
        # 갈 수 없는 경로인 경우, 0 출력
        if row[i] == inf:
            row[i] = 0
        print(row[i], end=" ")
    print()