Bellman-Ford algorithm

Bellman-Ford algorithm is an algorithm for finding the shortest paths between nodes in a graph. Given a initial node, it finds the shortest path to every nodes in a graph. The difference with Djisktra is that it accepts edges with negative values.

The algorithm uses dynamic programming: it computes the shortest paths to go to nodes in k steps (if node reachable in k step there score is infinity); for the k+1 step it uses the shortest path reachable in k steps and updated them using another pass over the edges of the graph.
Also the algorithm uses the fact that we can access every node from one origin node in a number of steps less than the number of nodes in the graph.

An animation from Wikipedia of the Bellman-Ford algorithm

Finding shortest paths from initial node 1 to every other nodes

The algorithm works as follow:

1. Initialize (initialisation):
   a. Shortest path for all nodes to infinity except for origin node that is initialized to 0 b. Predessor as an empty dictionnary

2. For i in 1 to the number of node - 1 (maximum moves to go from 1 node to another in the graph is less than the number of nodes):
   a. Copy the dictionnary of shortest path to another temporary dictionnary b. Loop over each edge of the graph and, in the temporary dictionnary, update the shortest path with the new value if it is better. The values for the originin node are taken from the shortest path dictionnrary (that is not updated in the loop); that protect over using updated information (otherwise it could move two of more steps in the same loop).

3. Return the list of distances from origin and the list of precedent nodes

Implementation

from collections import defaultdict

def bellman_ford(edges, origin_node, nb_nodes) -> int:   
    shortest_path, predecessor = defaultdict(lambda: float('inf')), dict()
    shortest_path[origin_node] = 0

    for i in range(nb_nodes-1):
        shortest_path_tmp = shortest_path.copy()
        for node_from, node_to, value in edges:
            if shortest_path[node_from] + value < shortest_path_tmp[node_to]:
                shortest_path_tmp[node_to] = shortest_path[node_from] + value
                predecessor[node_to] = node_from
        shortest_path = shortest_path_tmp

    return(shortest_path, predecessor)

def retrieve_path(predecessor, origin_node, final_node):
    # if node is origin it has no predecessor (special case) and just return it
    if final_node == origin_node:
        return([origin_node])
    
    # if node is not reachable return nothing
    if final_node not in predecessor:
        return(None)
    
    node, path_from_origin = final_node, []
    
    # while origin_node has not been reached add the node to the path and so to its predecessor
    while node != origin_node:
        path_from_origin = [node] + path_from_origin
        node = predecessor[node]
        
    return([origin_node] + path_from_origin)

edges = [(0, 1, 1), (1, 3, 2), (0, 3, 6), (1, 2, 1), (3, 1, 1)] # with edges values
distance, predecessor = bellman_ford(edges, 0, 4)
retrieve_path(predecessor, 0, 3)

[0, 1, 3]