Bellman–Ford Algorithm – A Complete Guide

The Bellman-ford algorithm is a well-known algorithm that solves the single-source shortest paths problem in a weighted directed graph. It is especially useful for cases when the graph has negative weight edges. Unlike Dijkstra’s algorithm, the Bellman-ford algorithm works even when edges in the graph are allowed to have negative weights and can also determine if the graph contains any negative weight cycles.

This guide will take you through a detailed exploration of the Bellman-Ford algorithm, starting with its foundations, workings, handling of negative weight cycles, pseudocode, variations from Dijkstra’s algorithm, code implementations in multiple languages, complexity analysis, and applications.

What is the Bellman-Ford Algorithm?

The Bellman-Ford algorithm determines the shortest paths from a single source vertex to all other vertices in a weighted graph. It does this by considering all edges in turn for each of the vertices. This paves the way for its notable feature of being able to handle graphs with negative weight edges. This distinguishes it from algorithms like Dijkstra’s, which work only for non-negative edge weights.

Bellman-Ford algorithm can be used on both weighted and unweighted graphs. In this algorithm, If there is a negative cycle in the graph, it is impossible to find the shortest path. The path’s cost will keep going down even while its length grows if we keep going around the negative cycle indefinitely. Bellman-Ford algorithm can therefore also identify negative cycles, which is a crucial aspect.

The Bellman-Ford algorithm is based on the principles of dynamic programming. It computes the shortest paths by iteratively relaxing every edge. Relaxation is updating the distance and predecessor values if a better path is found, in which further vertices can be connected only after relaxing that edge. The algorithm operates with iterations and in each of them goes through all edges, trying to “relax” them. This continues until no more updates are made for any vertex in the passes.

Characteristics:

• Works with both directed and undirected graphs.
• Detects negative weight cycles (a cycle whose total weight is negative) 
• Bellman-Ford is one of the well-known single-source shortest-path algorithms. 
• Does not guarantee the fastest runtime but guarantees correctness even for challenging cases.

The foundation of the Bellman-Ford algorithm is dynamic programming. It relaxes each edge to determine the shortest pathways step-by-step. Comparing and updating the shortest path estimate if a shorter path is discovered is the process known as relaxation. The method checks every edge and attempts to improve the shortest path estimate throughout each iteration. Here are the step-by-step workings of the Bellman-Ford algorithm:

Step 1: Initialisation

Set the distance from the source vertex to itself as 0, and to all other vertices as infinity.

for each vertex v in Graph:

        if v == source:

            distance[v] = 0

        else:

            distance[v] = ∞

Step 2: Relaxing the edges

For each edge, if the distance to the destination vertex can be shortened by going through the source vertex, update the destination’s distance.

for i from 1 to |V|-1:

        for each edge (u, v) in Graph:

            if distance[u] + weight(u, v) < distance[v]:

                distance[v] = distance[u] + weight(u, v)

Step 3: Check for Negative Cycles

Repeat the relaxation step V−1 times for each edge in the graph, where V is the number of vertices. Complete one more relaxing step following V−1 iterations. A negative weight cycle exists if any distance is updated.

for each edge (u, v) in Graph:

        if distance[u] + weight(u, v) < distance[v]:

            print “Graph contains a negative-weight cycle”

            return

Step 4: Shortest paths

The final step is to return the shortest path. If there are no negative cycles in the graph, the shortest path from the source node to all other nodes of the graph is returned.

return distance

How does Bellman-Ford Algorithm Handle Negative Weight Edges & Cycles?

Bellman-Ford algorithm has a key strength in handling the negative weight edges and cycles in the graph. Let’s see how it handles both:

• Negative Weight Edges

Negative weight edges can be present in graphs if the existence of certain transitions or paths would mean a decrease in cost (or distance) from what has already been computed. The Bellman-Ford correctly computes the shortest path even when such edges exist by allowing for multiple relaxations of edges.

• Negative Weight Cycles

A negative weight cycle is when a cycle in the graph has a total sum of weights that is negative. In this situation, no shortest path will exist because the algorithm could keep reducing the path cost by travelling around the cycle indefinitely.

• If after V−1 relaxations no edges can be relaxed and some can still be relaxed, then a negative weight cycle is present.
• The Bellman-Ford algorithm discovers this and indicates the presence of negative weight cycles by returning a special value to the user so that it should be thought of as a way of warning that, in such cases, the shortest path cannot be computed in a well-defined way.

Pseudocode of Bellman-Ford Algorithm

Here is the pseudocode for the bellman-ford algorithm:

function BellmanFord(Graph, source):

    // Step 1: Initialise distances

    for each vertex v in Graph:

        if v == source:

            distance[v] = 0

        else:

            distance[v] = ∞

    // Step 2: Relax edges |V|-1 times

    for i from 1 to |V|-1:

        for each edge (u, v) in Graph:

            if distance[u] + weight(u, v) < distance[v]:

                distance[v] = distance[u] + weight(u, v)

    // Step 3: Check for negative-weight cycles

    for each edge (u, v) in Graph:

        if distance[u] + weight(u, v) < distance[v]:

            print “Graph contains a negative-weight cycle”

            return

    // Shortest Path

    return distance

Explanation:

• Initialisation: The distance to the source is set to 0, and all other distances are initialised to infinity.
• Relaxation: For each edge, check if a shorter path can be found. If so, update the shortest path estimate.
• Negative Cycle Check: After relaxing the edges V−1 times, check once more for negative-weight cycles.

Bellman-Ford Algorithm Example

For this example, consider a graph with 5 vertices (A, B, C, D, E) with the following edges having weights:

A -> B (weight 2)

A -> C (weight 3)

B -> D (weight 1)

C -> D (weight 6)

B -> E (weight 4)

D -> E (weight -1)

From the given graph weights, we will run the Bellman-Ford algorithm to determine the shortest path from vertex (node) A to all other vertices (nodes).

Step 1: Initialisation

The first step is to initialise all other vertices’ distances to infinity (∞) and the distance to the source vertex A to 0. We also keep track of the parent of each vertex (used to reconstruct paths).

Step 2: Relaxing the edges

In this step, we try to discover the shortest path to each vertex by relaxing each edge in the graph. V is the number of vertices, and we repeat this method V−1 times. This makes sure we take into consideration all potential shortest paths.

Iteration 1:

• A -> B (distance(B) = min(∞, 0 + 2) = 2
• A -> C (distance(C) = min(∞, 0 + 3) = 3
• B -> D (distance(D) = min(∞, 2 + 1) = 3
• C -> D (distance(D) = min(3, 3 + 6) = 3 (no change)
• B -> E (distance(E) = min(∞, 2 + 4) = 6
• D -> E (distance(E) = min(6, 3 + (-1)) = 2

Iteration 2:

• A -> B (distance(B) = 2), no change
• A -> C (distance(C) = 3), no change
• B -> D (distance(D) = 2), no change
• C -> D (distance(D) = 3), no change
• B -> E (distance(E) = 2), no change
• D -> E (distance(E) = 2), no change

Iteration 3: All distances are unchanged after the third iteration of the algorithm.

Iteration 4: All distances are unchanged after the fourth iteration of the algorithm.

Step 3: Checking negative cycles

We now check the graph to see if there are any negative weight cycles following the V−1 iterations. To do this, try to relax each edge only once more. If any distance can be reduced further, it means that the graph contains a negative weight cycle.

In our example, 

• A -> B (distance(B) = 2), no change
• A -> C (distance(C) = 3), no change
• B -> D (distance(D) = 2), no change
• C -> D (distance(D) = 3), no change
• B -> E (distance(E) = 2), no change
• D -> E (distance(E) = 2), no change

Since no distances can be further reduced, we confirm that the graph does not contain any negative weight cycles, and can now move to determine shortest paths.

Step 4: Shortest paths

We can now output the shortest paths from vertex A to every other vertex after the relaxation is finished and it is verified that there are no negative weight cycles.

From the above table, we can finally output our shortest paths as:

• The shortest path from A to B is A -> B with a distance of 2.
• The shortest path from A to C is A -> C with a distance of 3.
• The shortest path from A to D is A -> B -> D with a distance of 3.
• The shortest path from A to E is A -> B -> D -> E with a distance of 2.

Difference between Dijkstra’s and Bellman Ford’s Algorithm

Several differences differentiate Dijkstra’s algorithm from the Bellman-Ford algorithm. Below are some of the common and main differences between them:

Code Examples

We will now understand the workings of the Bellman-Ford algorithm through code examples in different languages.

Bellman-Ford Algorithm Implementation in C

Code:

Output:

Vertex Distance from Source

0 0

1 2

2 3

3 3

4 2

Bellman-Ford Algorithm Implementation in C++

Code:

Output:

Bellman-Ford Algorithm Implementation in Java

Code:

Output:

Vertex Distance from Source

Explanation:

• In all three example codes, firstly all vertices in the distance array are initialised to infinity (or the maximum value), and the source vertex is set to 0.
• We then update the distances based on edge weights by iterating over all edges V−1 times, where V is the number of vertices.
• A final check is performed by trying to relax all edges one more time following V−1 iterations. If there is still a reduction in distance, there is a negative-weight cycle present. 
• Finally, the shortest path between the source vertex and each of the remaining vertices is printed.

Complexity Analysis of Bellman-Ford Algorithm

Time Complexity

The Bellman-Ford algorithm has a time complexity of O(V * E). Let’s see how and when:

• Best Case Time Complexity:

In the best case O(V * E), the Bellman-Ford will still run as it has to go through the relaxation step for all edges, even if no updates are required after the first few iterations. It does not stop prematurely like Dijkstra’s algorithm when all shortest paths have been found; therefore, the algorithm goes on V−1 iterations even if the solution has stabilised earlier. 

For example, in case the input graph contains no negative weight edges and after one relaxation all distances are computed, Bellman-Ford would still go ahead with the remaining V−2 iterations.

• Worst Case Time Complexity: 

The worst case for the Bellman-Ford algorithm is when the graph has V large number of edges E relative to vertices (such as in a dense graph), the graph contains negative weight edges and a full set of V−1 relaxations must be done, the graph may have a negative weight cycle but still completes all relaxation steps before detecting that cycle. Therefore, the time complexity in the worst case will remain O(V * E).

Space Complexity

The Bellman-Ford algorithm has an O(V + E) space complexity.

• Distance Array (O(V)):

To store the shortest path estimates from the source vertex to each other vertex, the method keeps track of a distance array. O(V) space is required for this array, where V is the number of vertices.

• List of Edges (O(E)):

Typically, the graph is shown as an edge list, with each edge connecting two vertices assigned a weight. O(E) space is needed in the edge list to hold all of the edges.

As a result, O(V + E) is the total space complexity, taking into consideration the edge list and distance array storage.

Applications of Bellman-Ford Algorithm

Various domains such as computer networks, distributed systems, optimisation problems, etc., make extensive use of the Bellman-Ford algorithm. Here are various applications of the Bellman-Ford algorithm:

1. Computer Networks: The algorithm is commonly used in distance vector routing protocols of computer networks such as the Routing Information Protocol (RIP) to calculate the shortest mesh network based on weighted edges. 
2. Currency Arbitrage: Negative cycles are regarded as successive trades that can be completed for a profit and can therefore be classified using the Bellman-Ford algorithm for negative cycle detection. 
3. Distributed Systems: This algorithm could be useful for solving the problem in a distributed computer system where processes work together but need to communicate with each other and explore the best paths. 
4. Pathfinding in Games: It can be applied in games for spatial pathfinding across different game objects or entities with fouls and penalty points incurred for movement through specific paths toward the goals. 
5. Arbitrage Detection: In undertaking loss minimisation in a network of capital flow graphs, arbitrage detection involves locating negative weight cycles. 
6. Detecting Negative Weight Cycles: The algorithm detects negative weight cycles in a graph, which may be a sign of problems such as financial arbitrage or unsustainable activities.
7. Operations Research: As far as network design optimisation or logistics practice is concerned the Bellman-Ford approaches aid in network routing for the minimum path problems where the distance cost or delay is the most in certain paths used.

Conclusion

The Bellman-Ford algorithm is an important part of graph theory, especially in the case of negative edge-weighted graphs. It guarantees the validity of the shortest path in these cases and even finds negative weight cycles. However, it will cease being the best algorithm for large-scale problems, but only positive weights will have Dijkstra’s ability’s scope. This is particularly useful in a multiplicity of fields. 

Be it in computer networks, financial markets, games, or any others, Bellman-Ford is an algorithm that represents the basics of dynamic programming applicable in solving non-trivial graph problems. To sum up, the best way to quickly explain the key algorithm for solving negative weights or negative cycles is the Bellman-Ford algorithm.