Published on Saturday 22 October 2022
Tags: python7 code5 algorithm3
Bellman-Ford algorithm [Python Code]
The Bellman-Ford algorithm finds the shortest path from a given source node to all other nodes allowing edges with negative weights. Here's a ready to use Python code implementing it.
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
'''