Ingap.dev - A Personal Dev Blog

I would spend 55 minutes defining the problem and then five minutes solving it. (Albert Einstein)

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?
  • Python Code 1: using a (square) distance matrix as input
  • Example 1.1: Find the shortest path
  • Example 1.2: Negative cycle detection
  • Python Code 2: using a (square) distance matrix as input
  • Example 2.1: Find the shortest path
  • Example 2.2: Negative cycle detection
  • 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
    '''