Ingap.dev - A Personal Dev Blog

Table of Content

What is the Bellman-Ford algorithm used for?

The Bellman-Ford algorithm finds the shortest path from a given source node to all other nodes allowing edges with negative weights. Here, "shortest path" means the path with the lowest cumulative weight along it. The algorithm has a time complexity of O(V*E), where V is the number of vertices and E is the number of edges.

It's possible to bump into negative cycles, i.e. circular paths (where start and end node are the same) with a resulting negative cumulative weight. In these cases, the shortest path will be indefinitely low, so in this case all following Python functions will return None.

Python Code 1: using a (square) distance matrix as input

The so-called distance matrix can be used to represent transitions between the i-th node (corresponding to the i-th row) and the j-th node (corresponding to the j-th column). The transition weight is therefore given by the (i, j) element. The time complexity will be O(N^3), with N being the matrix length.

Here's the Python function definition:

def bellman_ford(matrix, source):
    '''
    matrix: square distance matrix; the (i,j) elements is the distance between
    the source node i and the destination node j. 
    source: the source node index
    
    It returns None if shortest path from source to all other nodes can be
    arbitrarily low (ideally tends to -inf) because of negative cycles.
    Otherwise the array of shortest distances from source to all other nodes
    is returned.
    '''
    
    n, inf = len(matrix), float("inf")
    v = range(n)
    dist = [inf for _ in v]
    dist[source] = 0
    for _ in range(n - 1):
        for i in v:
            for j in v:
                w = matrix[i][j]
                if dist[i] != inf and dist[i] + w < dist[j]:
                    dist[j] = dist[i] + w
                    
    for i in v:
        for j in v:
            w = matrix[i][j]
            if dist[i] != inf and dist[i] + w < dist[j]:
                return None
            
    return dist

Example 1.1: Find the shortest path

source = 0
matrix = [[0,1,2,3,5],
          [2,0,-1,1,-1],
          [1,6,0,13,2],
          [1,2,1,0,-1],
          [3,3,2,4,0]]
 
print(bellman_ford(matrix, source))
 
'''
OUTPUT: [0, 1, 0, 2, 0]
 
I.e. shortest distance
from 0 to 0 is 0
from 0 to 1 is 1
from 0 to 2 is 0
from 0 to 3 is 2
from 0 to 4 is 0
'''

Example 1.2: Negative cycle detection

source = 0
matrix = [[0,1,2,3,5],
          [2,0,-7,1,-1],
          [1,6,0,13,2],
          [1,2,1,0,-1],
          [3,3,2,4,0]]
 
print(bellman_ford(matrix, source))
 
'''
OUTPUT: None
 
Negative cycle detected! (E.g. 0->1->2->0):
from 0 to 1: +1
from 1 to 2: -6
from 2 to 0: -5
'''

Python Code 2: using a (square) distance matrix as input

If a distance matrix would be too sparse because connections only involve fewer nodes, you could use some dictionary (here trans_dict). Here, the keys are tuples (i, j) and the values are the edges weights from node i to j. For example, trans_dict[(3,4)] gives the edge weight from node 3 to node 4. Note: if you like, you can also use some other labels instead of integers for nodes…

def bellman_ford(trans_dict, source):
    '''
    trans_dict: the (i,j) key points to the edge weight connecting node i to
    node j.
    source: the source node index
    
    It returns None if shortest path from source to all other nodes can be
    arbitrarily low (ideally tends to -inf) because of negative cycles.
    Otherwise the array of shortest distances from source to all other nodes
    is returned.
    '''
 
    nodes, inf = set([n for trans in trans_dict for n in trans]), float("inf")
    n = len(nodes)
    v = range(n)
    dist = [inf for _ in v]
    dist[source] = 0
    for _ in range(n - 1):
        for i,j in trans_dict:
            w = trans_dict[(i,j)]
            if dist[i] != inf and dist[i] + w < dist[j]:
                dist[j] = dist[i] + w
                    
    for i,j in trans_dict:
        w = trans_dict[(i,j)]
        if dist[i] != inf and dist[i] + w < dist[j]:
            return None
            
    return dist

Example 2.1: Find the shortest path

source = 0
trans_dict = {}
trans_dict[(0,0)] = 0
trans_dict[(0,1)] = 1
trans_dict[(0,2)] = 2
trans_dict[(0,3)] = 3
trans_dict[(0,4)] = 5
trans_dict[(1,0)] = 2
trans_dict[(1,1)] = 0
trans_dict[(1,2)] = -7
trans_dict[(1,3)] = 1
trans_dict[(1,4)] = -1
trans_dict[(2,0)] = 1
trans_dict[(2,1)] = 6
trans_dict[(2,2)] = 0
trans_dict[(2,3)] = 13
trans_dict[(2,4)] = 2
trans_dict[(3,0)] = 1
trans_dict[(3,1)] = 2
trans_dict[(3,2)] = 1
trans_dict[(3,3)] = 0
trans_dict[(3,4)] = -1
trans_dict[(4,0)] = 3
trans_dict[(4,1)] = 3
trans_dict[(4,2)] = 2
trans_dict[(4,3)] = 4
trans_dict[(4,4)] = 0
 
print(bellman_ford(trans_dict, source))
 
'''
OUTPUT: None
 
Negative cycle detected! (E.g. 0->1->2->0):
from 0 to 1: +1
from 1 to 2: -6
from 2 to 0: -5
'''

Example 2.2: Negative cycle detection

source = 0
trans_dict = {}
trans_dict[(0,0)] = 0
trans_dict[(0,1)] = 1
trans_dict[(0,2)] = 2
trans_dict[(0,3)] = 3
trans_dict[(0,4)] = 5
trans_dict[(1,0)] = 2
trans_dict[(1,1)] = 0
trans_dict[(1,2)] = -1
trans_dict[(1,3)] = 1
trans_dict[(1,4)] = -1
trans_dict[(2,0)] = 1
trans_dict[(2,1)] = 6
trans_dict[(2,2)] = 0
trans_dict[(2,3)] = 13
trans_dict[(2,4)] = 2
trans_dict[(3,0)] = 1
trans_dict[(3,1)] = 2
trans_dict[(3,2)] = 1
trans_dict[(3,3)] = 0
trans_dict[(3,4)] = -1
trans_dict[(4,0)] = 3
trans_dict[(4,1)] = 3
trans_dict[(4,2)] = 2
trans_dict[(4,3)] = 4
trans_dict[(4,4)] = 0
 
print(bellman_ford(trans_dict, source))
 
'''
OUTPUT: [0, 1, 0, 2, 0]
 
I.e. shortest distance
from 0 to 0 is 0
from 0 to 1 is 1
from 0 to 2 is 0
from 0 to 3 is 2
from 0 to 4 is 0
'''