Bellman Ford Algorithm

Problem Statement

Given a weighted and directed graph of V vertices and E edges. An edge is represented as [ai, bi, wi], meaning there is a directed edge from ai to bi having weight wi. Find the shortest distance of all the vertices from the source vertex S. If a vertex can't be reached from the S then mark the distance as 10^9.

If the graph contains a negative cycle then return -1.

Examples

Example 1:

Input: V = 6,
       Edges = [
                [3, 2, 6],
                [5, 3, 1],
                [0, 1, 5],
                [1, 5, -3],
                [1, 2, -2],
                [3, 4, -2],
                [2, 4, 3]
               ]
       S = 0

Output: 0 5 3 3 1 2

Explanation:
For node 1, shortest path is 0->1 (distance = 5)
For node 2, shortest path is 0->1->2 (distance = 3)
For node 3, shortest path is 0->1->5->3 (distance = 3)
For node 4, shortest path is 0->1->5->3->4 (distance = 1)
For node 5, shortest path is 0->1->5 (distance = 2)

Theory

The Bellman-Ford algorithm is a classic algorithm used to compute the shortest paths from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, it can handle graphs with negative weight edges as long as there are no negative weight cycles reachable from the source.

Different Approaches

1️⃣ Bellman Ford Algorithm

Intuition

The first thing that comes to mind when the requirement is to find shortest distance of all vertices from the source vertex S is Dijkstra's Algorithm. But this problem suggests that graphs can contain negative edges for which the Dijkstra's algorithm will fail.

To solve such issue, the Bellman Ford Algorithm will come in picture. It not only works when the graph contains negative edges, but also helps identify if the graph contains negative cycle (a cycle where sum of all weights is negative). The algorithm finds the minimum distance to reach any node by performing N-1 times Edge Relaxation (where N is the number of nodes in the graph). Though Bellman Ford Algorithm is more versatile, it is slower when compared to Dijkstra's Algorithm.

Edge Relaxation:

Consider the distance to reach node u and node v (via paths explored till now) be dist[u] and dist[v] respectively. If the distance taken to reach node v via some node u (dist[u] + wt) is smaller than the known distance to reach node v (dist[v]), then a shorter path to reach node v is found, which passes via node u. Thus, we update the distance to reach node v (dist[v]) to dist[u] + wt. This process of updating the distance is known as Edge Relaxation.

Why exactly N-1 iterations?

Longest Path in a Graph: The longest possible path without cycles in a graph with N nodes consists of (N-1) edges. And during each iteration, the Bellman-Ford algorithm updates the shortest path information for one more edge in the path.
Ensuring All Paths Are Considered: By repeating the relaxation process (N-1) times, the algorithm ensures that all vertices are updated based on paths that could extend up to (N-1) edges.

How to detect a negative cycle in the graph?

It is already known to us that if a graph has negative cycle, the edge relaxation can be done for an infinite number of times. But the algorithm suggests that all the edges will be relaxed after exactly (N-1) iterations.
Thus in order to check the existence of a negative cycle, an extra iteration can be performed to check if the edge relaxation is possible or not.
If in the extra iteration, the edge relaxation was possible, a negative cycle is confirmed in the graph.

Algorithm:

Set the distance to the starting node as 0 and to all other nodes as infinity.
On all the edges, perform Edge Relaxation for (N-1) times updating the distances of all nodes.
To detect if negative cycle exists, try performing edge relaxation on all the edges once more.
If for any edge, relaxation was possible, the graph contains a negative cycle.

Approach:

Initialize a distance array with a very large value (1e9) for all vertices. Set the distance of the source vertex to 0.
Perform edge relaxation on all edges for V-1 times, where V is the number of vertices i.e., check if the known distance to the destination vertex can be minimized by taking the edge. If yes, update the distance.
Perform an additional iteration over all edges to check for negative weight cycles. If any distance can still be minimized, a negative cycle exists in the graph, and the algorithm returns {-1}.
Return the distance array, which contains the shortest distances from the source to all other vertices, or {-1} if a negative cycle is detected.

Problem Statement

Examples

Theory