플로이드-워셜 알고리즘

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

1 개요

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

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

2 동작 원리

알고리즘은 다음과 같은 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)이다.

3 예시

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

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

이때, 플로이드-워셜 알고리즘을 적용하여 각 단계별로 경유 정점을 바꾸어가며 모든 정점 쌍 (i, j)에 대한 최단 경로를 계산한다. 초기 행렬과 각 단계에서의 비교 및 갱신 내역은 다음과 같다.

3.1 초기 행렬 (k=0, 아무 경유점 없음)

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

3.2 단계 1: 중간 정점 k = A

모든 i, j 쌍에 대해 다음을 비교한다: d[i][j] > d[i][A] + d[A][j] 인 경우 갱신

• A → A: 0 vs 0 + 0 → 그대로 유지
• A → B: 2 vs 0 + 2 → 그대로 유지
• A → C: 10 vs 0 + 10 = 10 → 그대로 유지
• B → A: ∞ vs ∞ + 0 → 그대로 유지
• B → B: 0 vs ∞ + 2 → 그대로 유지
• B → C: 3 vs ∞ + 10 → 그대로 유지
• C → A: ∞ vs ∞ + 0 → 그대로 유지
• C → B: ∞ vs ∞ + 2 → 그대로 유지
• C → C: 0 vs ∞ + 10 → 그대로 유지

→ 변화 없음

3.3 단계 2: 중간 정점 k = B

• A → A: 0 vs 2 + ∞ → 유지
• A → B: 2 vs 2 + 0 → 유지
• A → C: 10 vs A → B + B → C = 2 + 3 = 5 → 갱신됨
• B → A: ∞ vs 0 + ∞ → 유지
• B → B: 0 vs 0 + 0 → 유지
• B → C: 3 vs 0 + 3 → 유지
• C → A, C → B, C → C 모두 ∞ + 무한 → 유지

3.4 단계 3: 중간 정점 k = C

• 모든 경로에 대해:
• A → C: 5 vs 5 + 0 → 유지
• 나머지 조합도 모두 ∞ 또는 기존 값보다 크거나 같음 → 유지

3.5 최종 행렬

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

3.6 단계별 변화 요약

경로	초기값	k=A 이후	k=B 이후	k=C 이후
A → A	0	0	0	0
A → B	2	2	2	2
A → C	10	10	5	5
B → A	∞	∞	∞	∞
B → B	0	0	0	0
B → C	3	3	3	3
C → A	∞	∞	∞	∞
C → B	∞	∞	∞	∞
C → C	0	0	0	0

단 하나의 갱신이 발생한 경로는 A → C이며, 중간 정점 B를 통해 기존 10에서 5로 줄어들었다. 나머지 경로는 중간 정점을 경유하더라도 비용이 감소하지 않으므로 그대로 유지된다.

4 구현

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

5 특징

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

6 한계

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

7 같이 보기

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

8 참고 문헌

• 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.