Editing Bellman–Ford algorithm (section)

== Algorithm ==
[[File:Bellman-Ford worst-case example.svg|thumb|In this example graph, assuming that A is the source and edges are processed in the worst order, from right to left, it requires the full {{math|&#124;''V''&#124;−1}} or 4 iterations for the distance estimates to converge. Conversely, if the edges are processed in the best order, from left to right, the algorithm converges in a single iteration.]]

Like [[Dijkstra's algorithm]], Bellman–Ford proceeds by [[Relaxation (iterative method)|relaxation]], in which approximations to the correct distance are replaced by better ones until they eventually reach the solution.<ref>{{Cite web |title=Bellman-Ford - finding shortest paths with negative weights - Algorithms for Competitive Programming |url=https://cp-algorithms.com/graph/bellman_ford.html |access-date=2025-04-13 |website=cp-algorithms.com}}</ref><ref>{{Cite web |title=Bellman-Ford Algorithm |url=https://www.thealgorists.com/Algo/ShortestPaths/BellmanFord |access-date=2025-04-13 |website=www.thealgorists.com}}</ref> In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path.

However, Dijkstra's algorithm uses a [[priority queue]] to [[Greedy algorithm|greedily]] select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes ''all'' the edges, and does this <math>|V|-1</math> times, where <math>|V|</math> is the number of vertices in the graph.

In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra's algorithm. The intermediate answers depend on the order of edges relaxed, but the final answer remains the same.

Bellman–Ford runs in <math>O(|V|\cdot |E|)</math> [[Big O notation|time]], where <math>|V|</math> and <math>|E|</math> are the number of vertices and edges respectively.

 '''function''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source) '''is'''
 
     ''// This implementation takes in a graph, represented as''
     ''// lists of vertices (represented as integers [0..n-1]) and''
     ''// edges, and fills two arrays (distance and predecessor)''
     ''// holding the shortest path from the source to each vertex''
 
     distance := ''list'' of size ''n''
     predecessor := ''list'' of size ''n''
 
     ''// Step 1: initialize graph''
     '''for each''' vertex v '''in''' vertices '''do'''
         // Initialize the distance to all vertices to infinity
         distance[v] := '''inf'''
         // And having a null predecessor
         predecessor[v] := '''null'''
     
     // The distance from the source to itself is zero
     distance[source] := 0
 
     ''// Step 2: relax edges repeatedly''
     '''repeat''' |V|−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'''
             predecessor[v] := u
             ''// A negative cycle exists;''
             ''// find a vertex on the cycle''
             visited := ''list'' of size ''n'' initialized with '''false'''
             visited[v] := '''true'''
             '''while''' ''not'' visited[u] '''do'''
                 visited[u] := '''true'''
                 u := predecessor[u]
             ''// u is a vertex in a negative cycle,''
             ''// find the cycle itself''
             ncycle := [u]
             v := predecessor[u]
             '''while''' v != u '''do'''
                 ncycle := concatenate([v], ncycle)
                 v := predecessor[v]
             '''error''' "Graph contains a negative-weight cycle", ncycle
     '''return''' distance, predecessor

Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value.

The core of the algorithm is a loop that scans across all edges at every loop. For every <math>i \leq |V|-1</math>, at the end of the <math>i</math>-th iteration, from any vertex {{mvar|v}}, following the predecessor trail recorded in {{mvar|predecessor}} yields a path that has a total weight that is at most {{mvar|distance[v]}}, and further, {{mvar|distance[v]}} is a lower bound to the length of any path from source to {{mvar|v}} that uses  at most {{mvar|i}} edges.

Since the longest possible path without a cycle can be <math>|V|-1</math> edges, the edges must be scanned <math>|V|-1</math> times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length <math>|V|</math> edges has been found which can only occur if at least one negative cycle exists in the graph.

The edge (u, v) that is found in step 3 must be reachable from a negative cycle, but it isn't necessarily part of the cycle itself, which is why it's necessary to follow the path of predecessors backwards until a cycle is detected. The above pseudo-code uses a Boolean array (<code>visited</code>) to find a vertex on the cycle, but any [[Cycle detection|cycle finding]] algorithm can be used to find a vertex on the cycle.

A common improvement when implementing the algorithm is to return early when an iteration of step 2 fails to relax any edges, which implies all shortest paths have been found, and therefore there are no negative cycles. In that case, the complexity of the algorithm is reduced from <math>O(|V|\cdot |E|)</math> to <math>O(l \cdot |E|)</math> where <math>l</math> is the maximum length of a shortest path in the graph.