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
}