플로이드-워셜 알고리즘

플로이드-워셜 알고리즘(Floyd–Warshall algorithm, 플로이드-워셜 算法)은 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘으로, 음의 가중치를 가진 간선이 포함된 그래프에도 적용 가능하다.

개요

플로이드-워셜 알고리즘은 동적 계획법(Dynamic Programming)에 기반하여 그래프의 모든 정점 쌍 간 최단 경로를 효율적으로 계산하는 알고리즘이다. 1962년에 로버트 플로이드(Robert Floyd)가 워셜의 알고리즘을 기반으로 개선하여 발표하였다. 간선의 가중치가 음수일 수는 있지만, 음의 사이클이 존재해서는 안 된다.

그래프가 G = (V, E)일 때, 이 알고리즘은 각 정점 i에서 정점 j까지의 최단 거리 d[i][j]를 점진적으로 갱신하여 최종적으로 모든 최단 거리를 구한다.

동작 원리

알고리즘은 다음과 같은 3중 루프 구조로 구성된다.

1. 모든 i, j에 대해 d[i][j]를 초기화한다.

  * i = j이면 d[i][j] = 0
  * (i, j) 간선이 존재하면 d[i][j] = 가중치
  * 그 외에는 d[i][j] = ∞

2. 모든 정점 k를 중간 경유지로 고려하며, 다음을 수행한다:

  * d[i][j] = min(d[i][j], d[i][k] + d[k][j])

이 과정은 정점 개수가 n일 때 총 n^3 번의 연산이 이루어지며, 시간 복잡도는 O(n^3)이다.

예시

정점 A, B, C로 구성된 그래프가 다음과 같다고 하자:

• A → B (가중치 2)
• B → C (가중치 3)
• A → C (가중치 10)

초기 행렬:

	A	B	C
A	0	2	10
B	∞	0	3
C	∞	∞	0

중간 정점 B를 경유하면서 A → C 경로는 A → B → C = 2 + 3 = 5로 갱신된다.

최종 결과:

	A	B	C
A	0	2	5
B	∞	0	3
C	∞	∞	0

구현

def floyd_warshall(graph):
    dist = {u: {v: float('inf') for v in graph} for u in graph}
    for u in graph:
        dist[u][u] = 0
        for v, w in graph[u]:
            dist[u][v] = w

    for k in graph:
        for i in graph:
            for j in graph:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

특징

• 음의 가중치 허용
• 모든 정점 쌍 간 최단 거리 계산
• 동적 계획법 기반
• 간단한 행렬 기반 구현

한계

• 시간 복잡도 O(n^3)으로 정점 수가 많은 경우 비효율적
• 음의 사이클이 존재하면 정확한 결과를 제공하지 않음

같이 보기

• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 최단 경로 알고리즘
• 그래프 이론
• 동적 계획법

참고 문헌

• Floyd, R. W. (1962). Algorithm 97: Shortest Path. *Communications of the ACM*, 5(6), 345.
• Warshall, S. (1962). A Theorem on Boolean Matrices. *Journal of the ACM*, 9(1), 11–12.