알고리즘: 플로이드 와샬(Floyd-Warshall) - 모든 정점 쌍 최단 거리 구하기

플로이드 와샬이란?

그래프 내 모든 정점 쌍 (i, j)에 대한
최단 거리를 구하는 알고리즘.

한 정점에서 출발해서 다른 모든 정점으로 가는 것 뿐만 아니라, 모든 정점 간의 최단 경로를 한 번에 구할 수 있다.

플로이드-와샬 알고리즘은 3중 for문을 사용한 DP를 통해 구현된다. ($O(n^{3})$)

전제 조건

조건	설명
그래프 종류	방향 / 무방향 모두 가능
간선 가중치	음수 허용, 단 음수 사이클은 불가능
목적	모든 정점 쌍 (i, j)간의 최단 거리 (All-To-All)

동작 과정

플로이드 와샬 알고리즘은 다음과 같은 방식으로 진행된다.

1. 초기화
   모든 정점 간의 거리를 다음과 같이 초기화한다.
   - dist[i][j] = 0 (i == j)
   - dist[i][j] = w (i에서 j로 가는 간선의 가중치 w가 존재할 때)
   - dist[i][j] = INF (그 외의 경우)

2. 중간 노드 k에 대해 모든 경로를 갱신

모든 정점 쌍 (i, j)에 대해, i -> j로 가는 경로가 i -> k -> j로 우회했을 때 더 짧은지 확인한다.

for k in range(n):
	for i in range(n):
    	for j in range(n):
        	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

즉, 각 단계에서는 경로의 중간에 정점 k를 추가했을 때 더 짧은지를 확인하고 갱신한다.

음수 간선이 존재할 경우

음수 간선이 존재할 경우에도 다익스트라와 다르게, 동작 가능하다.

하지만, 음수 사이클이 존재할 경우 올바른 최단 거리를 구할 수 없다. 이 경우, dist[i][j] < 0인 정점이 생긴다.

구현

대표적인 플로이드 문제인 #11404. 플로이드를 봐보자.

각 정점간의 최단 거리를 모두 출력해야하는 문제이다. 앞서 설명한 동작 과정을 생각하면서 구현해보자.

def floyd_warshall(n: int, edges: list) -> list:
	dist = [[float("inf")] * n for _ in range(n)]
	for i in range(n): dist[i][i] = 0
	for s, e, c in edges: dist[s - 1][e - 1] = min(dist[s - 1][e - 1], c)
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dist[i - 1][j - 1] > dist[i - 1][k - 1] + dist[k - 1][j - 1]:
					dist[i - 1][j - 1] = dist[i - 1][k - 1] + dist[k - 1][j - 1]
	return dist

간선 정보를 바탕으로 비용을 초기화하고, 3중 for문을 통해 i에서 j로 가는 경로 중 k를 경유하는 경우가 더 짧다면 갱신하는 방식으로 동작하게 된다.