BellmanFord Algorithm¶
The BellmanFord algorithm finds shortest paths from a starting node to all nodes of the graph.
The algorithm reduces the distance by finding edges that shorten the paths until it is not possible to reduce any distances.
BellmanFord can process all kinds of graphs
The algorithm can process all kinds of graphs, provided that the graph does not contain a cycle with negative length. If the graph contains a negative cycle, the algorithm can detect this.
Implementation¶
Assume that the graph is stored as an edge list
edge that consists of tuples of the form$(a, b, w)$, meaing that there is an edge from node $a$ to node $b$ with weight $w$.
The algorithm consists of $n1$ rounds, and on each round the round the algorithm goes through all edges of the graph and tries to reduce the distances. The algorithm constructs an array $\text{distance}$ that will contain the distance from x to all nodes of the graph. The constant INF denotes an infinite distance.
$n = \text{number of vertices(nodes)}$, $m = \text{number of edges}$
1 2 3 4 5 6 7 8 9 10 11 12 

Time Complexity¶
$\Omicron(nm)$
Negative Cycles¶
The algorithm can also be used to check if the graph contains a cycle with negative length.
A negative cycle can be detected using the BellmanFord algorithm by running the algorithm for $n$ rounds
If the nth round reduces any distance, the graph contains a negative cycle.
Negative cycle in the whole graph
Note that this algorithm can be used to search for a negative cycle in the whole graph regardless of the starting node