Bellman-Ford Algorithm

Naowal Rahman

Graph theory is an important aspect of computer science; it is used to model pairwise relations between objects. Different algorithms are used to process graphs with different features. One such algorithm is the Bellman-Ford algorithm, which is of particular interest because of its ability to deal with and identify negative weight cycles.

Before discussing the Bellman-Ford algorithm, we first assert some definitions: a digraph is short for a directional graph; it is a graph made of vertices that are connected in a specific direction. The vertices can also be called nodes. The connectors between the vertices are called edges. On a directed graph, a path along a graph can only follow the direction of the edge while traversing. It cannot go the other way.

If a path starts from vertex 2, it can only go to vertex 3, and from there can only go to vertex 4. It cannot go to vertex 1 because that goes against the directed edge.

The way a node is represented in computers is through a 3-tuple or 3-long list containing the set \(\{u, v, w\}\). Here, \(u\) represents the source vertex, \(v\) represents the destination vertex, and \(w\) contains the weight associated with going from \(u\) to \(v\). To represent a weighted digraph containing all of those nodes, we use an adjacency matrix: a \(3\times n\) 2-dimensional array graph containing a number of sub-lists [u, v, w], representing all the nodes in the graph, where \(n\) is the number of nodes on the graph. A graph with 4 nodes and one unconnected node would look like the following:

graph = [[0, 1, 3],
         [1, 2, 2],
         [2, 3, 4]]
Graph representation

image

The purpose of Bellman-Ford is to compute the shortest path from a particular vertex (the source) to all of the other vertices in a weighted digraph. It is quite versatile because it can detect and deal with negative weights, which is something that other graph-traversing algorithms, like Dijkstra’s algorithm, cannot. This is when a particular edge or number of edges with negative weights causes a search to find the shortest path to continue on forever. It occurs in certain graphs where there are enough negative weights in a loop such that the cumulative sum of all the weights in that loop is negative. To further clarify, let us consider an example.

A negative weight cycle occurs when going from s to p

When attempting to calculate the shortest path from vertex \(s\) to vertex \(g\) via \(e\) and \(f\), the first step is to move from \(s\) to \(e\), since the cost of moving from \(s\) to \(e\) (2) is lower than the cost of moving from \(s\) to \(c\) (5). From \(e\) there is only one choiceto move to \(f\). However, once we are at \(f\), we have two choicesto move to \(g\), which costs 7, or move back to \(e\), which actually reduces our total cost by -6. An algorithm unlike Bellman-Ford is fit to pick the shortest path, so it will always move back to \(e\). As we continue, the total cost keeps on decreasing. Thus, the shortest path is never found.

This ability of the Bellman-Ford algorithm is the main reason for why it may be favored over other algorithms, as it otherwise has a relatively large time complexity of \(\mathcal O (VE)\) when compared to algorithms like Dijkstra’s Algorithm and breadth-first search, which have runtimes of \(\mathcal O ((V+E)\log V)\) and \(\mathcal{O}(V+E)\), respectively.

Bellman-Ford essentially overestimates the lengths of paths between the vertices in a graph, and then iterates over the graph, decreasing the estimates over time as it finds shorter paths. By the time the final iteration is complete, the result is optimized. The first iteration is an assigning of high distance values, and the second is a correction of those distances. The following iterations are for optimization. Thus the algorithm takes these steps:

  1. Given a weighted digraph, choose a starting vertex and assign infinity as the distance to all the other vertices.

  2. Traversing the graph, at each path correct the distances from infinity if they are inaccurate.

  3. Repeat step 1 for at most \(n-1\) times (the worst-case scenario), with \(n\) being the number of vertices in the graph.

  4. Check if a negative weight cycle is present.

When implementing this in code, there are three things to calculate or storethe path distance of each vertex, the shortest path, and its length. The path distance of each vertex will be stored in an array called distanceArray. The shortest path is obtained by associating each vertex with the previous one and backtracking from the destination vertex to the source vertex. The presence of a negative weight cycle is determined by comparing the total distance of the source vertex and the weight with the distance of the destination vertex. The algorithm is implemented as follows:

def bellmanFord(graph, source) distanceArray = list of size n previousArray = list of size n

for each vertex V in graph distanceArray[V] = infinite previousArray[V] = null distanceArray[source] = 0

for V - 1 times for each value (u, v, w) in graph tempDistance = distanceArray[u] + w if tempDistance < distanceArray[v] distanceArray[v] = tempDistance previousArray[v] = u

for each vertex V with values (u, v, w) in graph if distanceArray[u] + w < distanceArray[v] output "negative weight cycle detected"

return distanceArray, previousArray

The algorithm iterates over all of the edges for a total of \(V-1\) times, with \(V\) as the number of vertices, as indicated by the nested for-loop. Thus, as the number of vertices increases, the number of operations increases by \(E\), the number of edges, making the total time complexity \(O(VE)\).

The Bellman-Ford algorithm is useful in many communication scenarios. It works well in distributed systems, since the algorithm is node-based and distributed systems have require communication between components on multiple machines. In an area where distance and cost are major factors to consider, the Bellman-Ford excels. It is also used in distance-vector routing protocols, which determine the best path that packets of data should take based on distance. This is a situation where cost of routing data from one place to another can have significant impacts of speed of transfer and the presence of network traffic.

The Bellman-Ford algorithm is a unique and useful pathfinding algorithm in graph theory; in this paper, we shed some light on how Bellman-Ford works and its implementation. As noted, this may be flexibly applied to many problems.

Citations

    Dr. Roy Marsten, Emcien. “Is Graph Theory Key to Understanding Big Data?” Wired, Conde Nast, 7 Aug. 2015, https://www.wired.com/insights/2014/03/graph-theory-key-understanding-big-data/.