플로이드 워셜: 중간 정점을 하나씩 허용하는 모든 쌍 최단 거리
플로이드 워셜 알고리즘은 모든 정점 쌍의 최단 거리를 한꺼번에 구한다. 핵심은 현재 허용한 중간 정점의 집합을 조금씩 넓히는 동적 계획법이다. 출발점과 도착점은 고정한 채 “새 중간 정점 k를 거치면 더 짧아지는가”를 묻는다.
플로이드 워셜은 중간 정점을 허용하면서 정점 쌍의 거리를 갱신한다.
거리 행렬을 준비한다
dist[i][j]에는 직접 간선 비용을 넣고, 간선이 없으면 무한대, 자기 자신까지의 거리는 0으로 초기화한다. 같은 방향의 간선이 여러 개라면 최소 비용을 넣는다. 무방향 그래프는 양방향 칸을 채운다.
정점 k를 새로 허용할 때 경로는 k를 거치지 않는 기존 경로와, i→k 및 k→j를 이어 붙인 경로로 나뉜다. 따라서 dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])로 갱신한다.
def floyd_warshall(vertex_count, edges):
distance = [[float("inf")] * vertex_count for _ in range(vertex_count)]
for vertex in range(vertex_count):
distance[vertex][vertex] = 0
for start, end, cost in edges:
distance[start][end] = min(distance[start][end], cost)
for intermediate in range(vertex_count):
for start in range(vertex_count):
for end in range(vertex_count):
via = distance[start][intermediate] + distance[intermediate][end]
distance[start][end] = min(distance[start][end], via)
return distance
교육용 코드로 수치 범위와 무한대 덧셈이 안전한 표현을 가정한다. 고정 폭 정수를 쓴다면 존재하지 않는 두 경로를 더하지 않도록 검사하여 오버플로를 막아야 한다.
k 반복문이 바깥에 있어야 하는 이유
k단계의 행렬은 지금까지 허용한 정점들만 중간에 쓰는 최단 경로를 뜻한다. k를 가장 바깥에 둬야 모든 i,j 갱신이 같은 허용 집합에 대한 한 단계를 이룬다. 반복문 세 개를 아무 순서로 바꾸면 같은 알고리즘이 되는 것은 아니다.
A→B가 3, B→C가 2, A→C가 9라면 B를 중간에 허용하는 단계에서 A→C가 5로 바뀐다. 이때 두 부분 경로도 이전에 허용한 중간 정점만 사용한다는 상태 의미가 유지되어야 한다.
시간 O(V³), 공간 O(V²)라 정점 수가 큰 희소 그래프에는 부담이 크다. 여러 출발점에서 별도의 최단 경로 탐색을 실행하는 방식과 비교할 수 있다. 경로 복원을 원하면 다음 정점이나 중간 정점 정보를 추가로 저장한다.
음수 간선은 허용되지만 음수 사이클이 있으면 그 영향을 받는 쌍의 유한한 최단 거리가 없다. 종료 뒤 dist[k][k]<0인 정점으로 음수 사이클을 확인하고, 그 정점으로 갈 수 있고 거기서 나올 수 있는 쌍을 구별해야 한다. 단순한 숫자 행렬만 반환했다고 모든 값이 유효한 최단 거리인 것은 아니다.