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])
}
}
}
Author And Source
この問題について(Swift で Floyd-Warshall Algorithm (ワーシャル・フロイド法）使ってAPSP：All Pair Shortest Path（全点対最短経路問題）), 我々は、より多くの情報をここで見つけました https://qiita.com/snamiki1212/items/37d83b72550def18282a著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .