Find all shortest paths between two nodes in a graph using BFS.

find_all_shortest_paths.py

def find_all_shortest_paths(dic_node, n1, n2, step_threshold):
    return_paths = []
    visit_queue = [[n1]]
    # this can be updated to get all shortest paths for all visited nodes
    # for the shortest path from N1 to N2, all intermediate paths are also shortest paths between their respective nodes.
    visited_nodes_prev = set()
    visited_nodes = set()
    cur_distance = 0
    while len(visit_queue):
        cur_path = visit_queue.pop(0)
        if len(cur_path) >= step_threshold:
            break
        # update shortest paths
        if len(cur_path) > cur_distance:
            cur_distance = len(cur_path)
            visited_nodes.update(visited_nodes_prev)
        cur = cur_path[-1]
        if cur in dic_node:
            for node2 in dic_node[cur]:
                if node2 in visited_nodes:
                    continue
                if node2 == n2:
                    return_paths.append(cur_path + [node2,])
                    step_threshold = len(cur_path) + 1
                else:
                    visit_queue.append(cur_path + [node2,])
                    visited_nodes_prev.add(node2)
    return return_paths