Skip to content

Instantly share code, notes, and snippets.

@travishen
Last active September 7, 2021 20:59
Show Gist options
  • Save travishen/82e7a8aadf38b46f27652d758dc75261 to your computer and use it in GitHub Desktop.
Save travishen/82e7a8aadf38b46f27652d758dc75261 to your computer and use it in GitHub Desktop.
Bellman-Ford Algorithm Pseudo code
function BellmanFord(Graph, edges, source)
distance[source] = 0
for v in Graph
distance[v] = inf
predecessor[v] = undefind
for i=1...num_vertexes-1 // for all edges, if the distance to destination can be shortened by taking the
// edge, the distance is updated to the new lower value
for each edge (u, v) with wieght w in edges
tempDist = distance[v]
if tempDist < distance[v]
distance[v] = tempDist
predeccessor[v] = u
for each edge (u, v) with weight w in edges // scan V-1 times to ensure shortest path has been found
// for all nodes, and if any better solution existed ->
// there is a negative cycle!
if distance[u] + w < distance[v]
error: "Negative cycle detected"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment