Skip to content

Instantly share code, notes, and snippets.

@V8tr
Last active February 16, 2022 16:49
Show Gist options
  • Save V8tr/4e8792283e806d3d579e40f9c3051d86 to your computer and use it in GitHub Desktop.
Save V8tr/4e8792283e806d3d579e40f9c3051d86 to your computer and use it in GitHub Desktop.
Bellman Ford in an acyclic weighed undirected graph
struct Edge {
var u: Int
var v: Int
var weight: Int
func other(_ vertex: Int) -> Int {
return vertex == u ? v : u
}
}
class Graph {
private(set) var adj: [[Edge]]
let V: Int
init(_ V: Int) {
adj = Array(repeating: [], count: V)
self.V = V
}
func addEdge(_ e: Edge) {
adj[e.u].append(e)
adj[e.v].append(e)
}
}
// O(V*E)
func bellmanFord(_ graph: Graph, _ s: Int) -> [Int] {
let inf = 0x3f3f3f3f
var distTo = Array(repeating: inf, count: graph.V)
var q = [s]
distTo[s] = 0
func relax(_ v: Int) {
for e in graph.adj[v] {
let w = e.other(v)
if distTo[w] > distTo[v] + e.weight {
distTo[w] = distTo[v] + e.weight
q.append(w)
}
}
}
while !q.isEmpty {
let v = q.removeFirst()
relax(v)
}
return distTo
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment