Shortest Path Algorithm| Bellman — Ford | Graph With Negative Weights

4 min readNov 26, 2022

Imagine Google maps, we might want to see how much time will it take to reach all the nearby malls from our home, where some routes take longer time than the others. Now what if we want to see which mall will be the closest to us by time. So how can we find so?

Here, Bellman-ford algorithm might help. (Also read Dijsktra Algorithm.)

Brief:

Bellman ford is an algorithm used to find shortest path from a source node to all the other nodes in a directed graph with weighted edges. Here, each mall as well as our home can be considered as vertices and each route connecting those vertices can be considered as edges with the time being the weights.

This algorithm uses Bottom-up Dynamic Programming strategy by checking for all the possible routes and its weights by repetitively relaxing edges for n-1 times where n is the number of vertices.

It can also handle negative weights in a directed graph as well as positive weighted cycles, yielding the correct result.

So how it works?

It states that if we have n number of vertices in graph then we should update shortest path for all the edges for n-1 times.
Or in other words, for n-1 times, we go over each of the edges ( u,v,w), and we keep updating the shortest path for v with the Bellman-Ford relaxation rule (explained below) .

This algorithm uses the approach that we should first calculate the shortest path from source u to those vertices( v) which have at most 1 edge in the path. Then in next turn, we should calculate the shortest path from source u which have at most 2 edges in the path and so on, until n-1 paths are considered.

Note: We need to do this n-1 times since it is assumed that a shortest path can have at most n-1 edges, and cannot have cycles.

Steps in details:

Considering the below graph:

Define an array for all vertices to store the shortest path weights : d[].
Define a temporary array : temp[]
Start from source node,and mark d[src] = 0

Let’s take vertex 1 as our source node, then d[] and temp[]would look like:

4. Now lets repeat the below steps unless n-1 iterations are completed, for all edges with ( u , v , w) where u is the source node, v is the destination node and w is the weight to move from u to v:

Copy from array d[] to temp[]
Relax d[v] according to below relaxation rule:

if ( d[u]+ w ) < temp[v]:
    temp[v] = d[u] + w  # only change in the temp[] array

Copy the temp[] to d[] array.

During first iteration,

and copying from temp[], the array d[]would look like:

And this will continue for n-1 times.After completing the iterations for n-1 times, the resulting d[] would be:

Code Snippet:

from math import inf

def shortest_path (edges, src, n):
    d = [inf]*(n+1)
    d[src]=0
    temp = []
    
    for _ in range(n-1):
        temp=d[:]
        
        for u,v,w in edges:
            if d[u]+w < temp[v]:
                temp[v] = d[u]+w
 
        d = temp
        
    return d[1:] # since vertices are in range of 0 to n

print(shortest_path([[1,2,1],[1,3,5],[2,3,3],[3,4,-2]], 1, 4))

Time Complexity:

As we can see, for n-1 times, we are going over all the edges. So time complexity will be: O(n-1 * E) = O(E*V) where E is no of edges and V is the number of vertices, here it is n

Space Complexity: O(V)

Edge Case / Limitation:

Bellman -ford algorithm cannot find shortest path for weighted graph with negative cycles.

Example of negative cycle:
Below the graph represent a cycle whose total weights is negative:
-6 + 3 + 2 = -1

Although, bellman-ford fails to find the shortest path, it can still be used to detect negative cycles in the graph.

How? If after at most n-1 iterations, any vertex’s weight gets changed, it indicates a negative cycle including the vertex itself.

When to use?

When the graph is directed. If undirected graph, we can consider two sided edges from the nodes to make it directed graph.
When shortest path to reach all the nodes from a single source is required.
When all the weights can be negative.
To detect a negative cycle in the graph.
To find the shortest path from source with at most K number of paths in between.