Swift で Floyd-Warshall Algorithm (ワーシャル・フロイド法）使ってAPSP：All Pair Shortest Path（全点対最短経路問題）

備忘のメモ

NOTE

• 実装：２次元配列のDP

コード

// init
let INF = 1_000_000
var dp = [[Int]](repeating: [Int](repeating: INF, count: N), count: N) // set inf
for i in 0..<N { dp[i][i] = 0 } // zero reset
for (from, to, cost) in list { dp[from][to] = cost } // set initial val

// floyd-warshall
for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        }
    }
}