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

플로이드-워셜 알고리즘(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)
초기 행렬:
{| class="wikitable"
! ||A||B||C
|-
|A||0||2||10
|-
|B||∞||0||3
|-
|C||∞||∞||0
|}중간 정점 B를 경유하면서 A → C 경로는 A → B → C = 2 + 3 = 5로 갱신된다.

최종 결과:
{| class="wikitable"
! ||A||B||C
|-
|A||0||2||5
|-
|B||∞||0||3
|-
|C||∞||∞||0
|}
==구현==
<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.
==각주==
[[분류:알고리즘]]
[[분류:그래프 이론]]
[[분류:동적 계획법]]