BellmanFord Algorithm
The BellmanFord algorithm is a graph search algorithm that finds the shortest path between a given source vertex and all other vertices in the graph. This algorithm can be used on both weighted and unweighted graphs.
Like Dijkstra's shortest path algorithm, the BellmanFord algorithm is guaranteed to find the shortest path in a graph. Though it is slower than Dijkstra's algorithm, BellmanFord is capable of handling graphs that contain negative edge weights, so it is more versatile. It is worth noting that if there exists a negative cycle in the graph, then there is no shortest path. Going around the negative cycle an infinite number of times would continue to decrease the cost of the path (even though the path length is increasing). Because of this, BellmanFord can also detect negative cycles which is a useful feature.
Imagine a scenario where you need to get to a baseball game from your house. Along the way, on each road, one of two things can happen. First, sometimes the road you're using is a toll road, and you have to pay a certain amount of money. Second, sometimes someone you know lives on that street (like a family member or a friend). Those people can give you money to help you restock your wallet. You need to get across town, and you want to arrive across town with as much money as possible so you can buy hot dogs. Given that you know which roads are toll roads and which roads have people who can give you money, you can use BellmanFord to help plan the optimal route.
Instead of your home, a baseball game, and streets that either take money away from you or give money to you, BellmanFord looks at a weighted graph. The graph is a collection of edges that connect different vertices in the graph, just like roads. The edges have a cost to them. Either it is a positive cost (like a toll) or a negative cost (like a friend who will give you money). So, in the above graphic, a red arrow means you have to pay money to use that road, and a green arrow means you get paid money to use that road. In the graph, the source vertex is your home, and the target vertex is the baseball stadium. On your way there, you want to maximize the number and absolute value of the negatively weighted edges you take. Conversely, you want to minimize the number and value of the positively weighted edges you take. BellmanFord does just this.
Contents
Overview
The BellmanFord algorithm operates on an input graph, \(G\), with \(V\) vertices and \(E\) edges. A single source vertex, \(s\), must be provided as well, as the BellmanFord algorithm is a singlesource shortest path algorithm. No destination vertex needs to be supplied, however, because BellmanFord calculates the shortest distance to all vertices in the graph from the source vertex.
The BellmanFord algorithm, like Dijkstra's algorithm, uses the principle of relaxation to find increasingly accurate path length. BellmanFord, though, tackles two main issues with this process.
 If there are negative weight cycles, the search for a shortest path will go on forever.
 Choosing a bad ordering for relaxations leads to exponential relaxations.
The detection of negative cycles is important, but the main contribution of this algorithm is in its ordering of relaxations. Dijkstra's algorithm is a greedy algorithm that selects the nearest vertex that has not been processed. BellmanFord, on the other hand, relaxes all of the edges.
BellmanFord labels the edges for a graph \(G\) as \[e_1, e_2, ... , e_m,\]
and that set of edges is relaxed exactly \(V  1\) times, where \(V\) is the number of vertices in the graph.
Algorithm Psuedocode
The pseudocode for the BellmanFord algorithm is quite short.
This is high level description of BellmanFord written with pseudocode, not an implementation.
1 2 3 4 5 6 7 

The first for
loop sets the distance to each vertex in the graph to infinity. This is later changed for the source vertex to equal zero. Also in that first for
loop, the p
value for each vertex is set to nothing. This value is a pointer to a predecessor vertex so that we can create a path later.
The next for
loop simply goes through each edge (u, v)
in E
and relaxes it. This process is done V  1
times.
Relaxation Equation
Relaxation is the most important step in BellmanFord. It is what increases the accuracy of the distance to any given vertex. Relaxation works by continuously shortening the calculated distance between vertices comparing that distance with other known distances.
Take the baseball example from earlier. Let's say I think the distance to the baseball stadium is 20 miles. However, I know that the distance to the corner right before the stadium is 10 miles, and I know that from the corner to the stadium, the distance is 1 mile. Clearly, the distance from me to the stadium is at most 11 miles. So, I can update my belief to reflect that. That is one cycle of relaxation, and it's done over and over until the shortest paths are found.
This is relaxation equation.
Relax Equation
1 2 3 4relax(u, v): if v.distance > u.distance + weight(u, v): v.distance = u.distance + weight(u, v) v.p = u
Remember that the distance to every vertex besides the source starts at infinity, so a clear starting point for this algorithm is an edge out of the source vertex. Imagine that there is an edge coming out of the source vertex, \(S\), to another vertex, \(A\). This edge has a weight of 5. So, the if
statement in the relax function would look like this for the edge \((S, A)\):
\[ \text{if }A.distance > S.distance + weight(S, A), \]
which is the same as
\[ \text{if }\infty > 0 + 5 .\]
Since this is of course true, the rest of the function is executed. A.distance
is set to 5, and the predecessor of A
is set to S
, the source vertex.
Relaxation is safe to do because it obeys the "triangle inequality." Another way of saying that is "the shortest distance to go from \(A\) to \(B\) to \(C\) should be less than or equal to the shortest distance to go from \(A\) to \(B\) plus the shortest distance to go from \(B\) to \(C\)":
\[distance(A, C) \leq distance(A, B) + distance(B, C).\]
Detecting Negative Cycles
A very short and simple addition to the BellmanFord algorithm can allow it to detect negative cycles, something that is very important because it disallows shortestpath finding altogether. After the BellmanFord algorithm shown above has been run, one more short loop is required to check for negative weight cycles.
This psuedocode is written as a high level descrpition of the algorithm, not an implementation.
1 2 3 4 5 6 7 8 9 10 

Algorithm Proof
There are a few, short steps to proving BellmanFord. The first step shows that each iteration of BellmanFord reduces the distance of each vertex in the appropriate way. The second step shows that once the algorithm has terminated, if there are no negative weight cycles, the resulting distances are perfectly correct. The final step shows that if that is not the case, then there is indeed a negative weight cycle, which proves the BellmanFord negative cycle detection.
Step 1:
Claim: After interation \(i\), for all \(v\) in \(V\), \(v.d\) is at most the weight of every path from \(s\) to \(v\) using at most \(i\) edges.
Before iteration \(i\), the value of \(v.d\) is constrained by the following equation
\[v.d \leq min{w(p): p \leq i  1},\]
where \(w(p)\) is the weight of a given path and \(p\) is the number of edges in that path. Subsequent relaxation will only decrease \(v.d\), so this will always remain true. The \(i^\text{th}\) iteration will consider all incoming edges to \(v\) for paths with \(\leq i\) edges.
Step 2:
Claim: If the input graph does not have any negative weight cycles, then BellmanFord will accurately give the distance to every vertex \(v\) in the graph from the source.
An important thing to note is that without negative weight cycles, the shortest paths will always be simple. There will not be any repetition of edges. So, each shortest path has \(V^{*}\) vertices and \(V^{*}  1\) edges (depending on which vertex we are calculating distance for). More generally, \(V^{*} \leq V\), so each path has \(\leq V\) vertices and \(\leq V^{*}  1\) edges.
Consider the shortest path from \(s\) to \(u\), where \(v\) is the predecessor of \(u\). On the \((i  1)^\text{th} \) iteration, we've found the shortest path from \(s\) to \(v\) using at most \(i  1\) edges. \(v.distance\) is at most the weight of this path. So, \(v.distance + weight(u, v)\) is at most the distance from \(s\) to \(u\). On the \(i^\text{th}\) iteration, all we're doing is comparing \(v.distance + weight(u, v)\) to \(u.distance\). All that can possibly happen is that \(u.distance\) gets smaller. So, after the \(i^\text{th}\) iteration, \(u.distance\) is at most the distance from \(s\) to \(u\). And because it can't actually be smaller than the shortest path from \(s\) to \(u\), it is exactly equal.
Step 3:
Claim: BellmanFord can report negative weight cycles.
Using our Step 2, if we go back through all of the edges, we should see that for all \(v\) in \(V\), \(v.distance = distance(s, v)\). BellmanFord will only report a negative cycle if \(v.distance \gt u.distance + weight(u, v)\), so there cannot be any false reporting of a negative weight cycle.
If there is a negative weight cycle, then one of the edges of that cycle can always be relaxed (because it can keep on being reduced as we go around the cycle). Imagining that the edge in question is the edge \((u, v)\); that means that \(u.distance + weight(u, v)\) will actually be less than \(v.distance\), which will trigger a negative cycle report.
Complexity
As described above, BellmanFord makes \(E\) relaxations for every iteration, and there are \(V  1\) iterations. Therefore, the worstcase scenario is that BellmanFord runs in \(O(V \cdot E)\) time.
However, in some scenarios, the number of iterations can be much lower. For certain graphs, only one iteration is needed, and so in the best case scenario, only \(O(E)\) time is needed. An example of a graph that would only need one round of relaxation is a graph where each vertex only connects to the next one in a linear fashion, like the graphic below.
See also: big O notation.
Worst  Best  
BellmanFord  \(O(V \cdot E)\)  \(O(E)\) 
Applications
A version of BellmanFord is used in the distancevector routing protocol. This protocol decides how to route packets of data on a network. The distance equation (to decide weights in the network) is the number of routers a certain path must go through to reach its destination.
For the Internet specifically, there are many protocols that use BellmanFord. One example is the routing Information protocol. This is one of the oldest Internet protocols, and it prevents loops by limiting the number of hops a packet can make on its way to the destination. A second example is the interior gateway routing protocol. This proprietary protocol is used to help machines exchange routing data within a system.