# Bellman-Ford algorithm facts for kids

In computer science, **Bellman-Ford** is an algorithm used to compute the shortest distances and paths from a single node within a graph to all other nodes.

## Usage

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.

## Psuedocode

functionBellmanFord(listnodes,listedges,nodesource)is

distance := *list* predecessor := *list* // Predecessor holds shortest paths

// Step 1: initializefor eachnode ninnodesdo

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 repeatedlyrepeat|nodes|−1times:for eachedge (u, v)withweight winedgesdoifdistance[u] + w < distance[v]then

distance[v] := distance[u] + w predecessor[v] := u

// Step 3: check for negative-weight cyclesfor eachedge (u, v)withweight winedgesdoifdistance[u] + w < distance[v]thenerror"Graph contains a negative-weight cycle"returndistance, predecessor

*Kiddle Encyclopedia.*