Swift で Bellman-Ford Algorithm (ベルマンフォード法)使ってSSSP:Single Source Shortest Path(単一始点最短経路問題)
備忘用メモ
- Time Complexity: O(VE) (V: number of vertexes, E: number of edges)
// List starts from 1-index not zero-index.
func bellmanford (_ N: Int, _ graph: [Edge], _ start: Int) -> Int {
var dist = [Int](repeating: Int.max, count: N+1)
dist[start] = 0
for i in 1...N { // O(V)
var updated = false
for e in graph { // O(E)
if dist[e.from] == Int.max { continue }
if dist[e.to] > dist[e.from] + e.weight {
dist[e.to] = dist[e.from] + e.weight
updated = true
}
}
if !updated { break } // quick return: no more update
if i==N && updated { return -1 } // graph has negative cycle.
}
return dist[N]
}
struct Edge {
let from: Int
let to: Int
let weight: Int
}
Author And Source
この問題について(Swift で Bellman-Ford Algorithm (ベルマンフォード法)使ってSSSP:Single Source Shortest Path(単一始点最短経路問題)), 我々は、より多くの情報をここで見つけました https://qiita.com/snamiki1212/items/b2684b5a78bb35ff2c5c著者帰属:元の著者の情報は、元の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 .