플로이드 알고리즘(Floyd-Warshall)

[Taehyeon-Kim]

플로이드 알고리즘

모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘

let n = 5
let d = [[], [] ,[], [] ,[]] // 예시이므로 값을 채워놓지는 않았음

// 최단거리 테이블 초기화
// 1. 자기 자신으로 가는 거리는 0
// 2. 가지 못하는 곳은 Int.max(무한을 의미)
/* code */

// k가 가장 바깥에서 루프를 도는 것은 자명한 사실이다.
for k in 0..<n {
  for s in 0..<n {
    for t in 0..<n {
      d[s][t] = min(d[s][t], d[s][k] + d[k][t])
    }
  }
}