Bellman-Ford algorithm facts for kids
It is more robust than Dijkstra's algorithm because it is able to handle graphs containing negative edge weights. It may be improved by noting that, if an iteration of the main loop of the algorithm completes without making any changes, the algorithm can be immediately completed, as future iterations will not make any changes. Its runtime is time, where and are the number of nodes and edges respectively.
function BellmanFord(list nodes, list edges, node source) is
distance := list predecessor := list // Predecessor holds shortest paths
// Step 1: initialize for each node n in nodes do
distance[n] := inf // Initialize the distance to all nodes to infinity predecessor[n] := null // And having a null predecessor
distance[source] := 0 // The distance from the source to itself is zero
// Step 2: relax edges repeatedly repeat |nodes|−1 times: for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then
distance[v] := distance[u] + w predecessor[v] := u
// Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then error "Graph contains a negative-weight cycle" return distance, predecessor
Bellman-Ford algorithm Facts for Kids. Kiddle Encyclopedia.