플로이드-워셜 알고리즘 편집하기 (부분)

== 예시 ==
정점 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로 줄어들었다. 나머지 경로는 중간 정점을 경유하더라도 비용이 감소하지 않으므로 그대로 유지된다.