Bellman-Ford Algorithm

The Bellman-Ford 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 Bellman-Ford algorithm is guaranteed to find the shortest path in a graph. Though it is slower than Dijkstra's algorithm, Bellman-Ford 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, Bellman-Ford 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 Bellman-Ford to help plan the optimal route.

Graphical representation of routes to a baseball game

Instead of your home, a baseball game, and streets that either take money away from you or give money to you, Bellman-Ford 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. Bellman-Ford does just this.

The Bellman-Ford 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 Bellman-Ford algorithm is a single-source shortest path algorithm. No destination vertex needs to be supplied, however, because Bellman-Ford calculates the shortest distance to all vertices in the graph from the source vertex.

The Bellman-Ford algorithm, like Dijkstra's algorithm, uses the principle of relaxation to find increasingly accurate path length. Bellman-Ford, though, tackles two main issues with this process:

1. If there are negative weight cycles, the search for a shortest path will go on forever.
2. 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. Bellman-Ford, on the other hand, relaxes all of the edges.

Bellman-Ford 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.

The pseudo-code for the Bellman-Ford algorithm is quite short.

This is high level description of Bellman-Ford written with pseudo-code, not an implementation.

1
2
3
4
5
6
7

for v in V:
    v.distance = infinity
    v.p = None
source.distance = 0
for i from 1 to |V| - 1:
    for (u, v) in E:
        relax(u, v)

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 is the most important step in Bellman-Ford. 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 4

relax(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).\]

A very short and simple addition to the Bellman-Ford algorithm can allow it to detect negative cycles, something that is very important because it disallows shortest-path finding altogether. After the Bellman-Ford algorithm shown above has been run, one more short loop is required to check for negative weight cycles.

This pseudo-code is written as a high-level description of the algorithm, not an implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

for v in V:
    v.distance = infinity
    v.p = None
source.distance = 0
for i from 1 to |V| - 1:
    for (u, v) in E:
        relax(u, v)
for (u, v) in E:
    if v.distance > u.distance + weight(u, v):
        print "A negative weight cycle exists"

There are a few short steps to proving Bellman-Ford. The first step shows that each iteration of Bellman-Ford 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 Bellman-Ford 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.

On the \(i^\text{th}\) iteration

Step 2:

Claim: If the input graph does not have any negative weight cycles, then Bellman-Ford 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 the 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: Bellman-Ford 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)\). Bellman-Ford 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.

As described above, Bellman-Ford makes \(|E|\) relaxations for every iteration, and there are \(|V| - 1\) iterations. Therefore, the worst-case scenario is that Bellman-Ford runs in \(O\big(|V| \cdot |E|\big)\) time.

However, in some scenarios, the number of iterations can be much lower. For certain graphs, only one iteration is needed, and hence in the best case scenario, only \(O\big(|E|\big)\) 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:

This graph only needs one round of relaxation.

See also: big O notation.

A version of Bellman-Ford is used in the distance-vector 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 Bellman-Ford. 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.