1

More than 1 year has passed since last update.

# Swift で Bellman-Ford Algorithm (ベルマンフォード法）使ってSSSP：Single Source Shortest Path（単一始点最短経路問題）

Last updated at Posted at 2021-09-06

• 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
}
``````

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
1