플로이드-워셜 알고리즘 편집하기

플로이드-워셜 알고리즘(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)

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

=== 초기 행렬 (k=0, 아무 경유점 없음) ===
{| class="wikitable"
! ||A||B||C
|-
|A||0||2||10
|-
|B||∞||0||3
|-
|C||∞||∞||0
|}

=== 단계 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 → 그대로 유지

→ 변화 없음

=== 단계 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: 중간 정점 k = C ===
* 모든 경로에 대해:
* A → C: 5 vs 5 + 0 → 유지
* 나머지 조합도 모두 ∞ 또는 기존 값보다 크거나 같음 → 유지
=== 최종 행렬 ===
{| class="wikitable"
! ||A||B||C
|-
|A||0||2||5
|-
|B||∞||0||3
|-
|C||∞||∞||0
|}

=== 단계별 변화 요약 ===
{| class="wikitable"
! 경로 || 초기값 || 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로 줄어들었다. 나머지 경로는 중간 정점을 경유하더라도 비용이 감소하지 않으므로 그대로 유지된다.

==구현==
<syntaxhighlight lang="python">
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
</syntaxhighlight>
==특징==
*음의 가중치 허용
*모든 정점 쌍 간 최단 거리 계산
*동적 계획법 기반
*간단한 행렬 기반 구현
==한계==
*시간 복잡도 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.
==각주==
[[분류:알고리즘]]
[[분류:그래프 이론]]
[[분류:동적 계획법]]