'Implement BFS with cost function in pandas python

I am implementing a BFS algorithm for a shortest path on dictionary. Here is my sample input:

{1: [{'0': 1.5}, {'3,2': 6.09}, {'4': 7.9}],
 2: [{'5': 9.5}, {'0': 1.2}],
 3: [{'3': 2.4}]}

In above input 1,2,3 are nodes, '0','3,2','4','5','0','3' are Parent set and 1.5,6.09,7.9,9.5,1.2,2.4 are cost of the paths. I want to find the shortest path depends upon cost.

Here is a simple BFS:

from queue import Queue

def BFS(adj_list, start_node, target_node):
    # Set of visited nodes to prevent loops
    visited = set()
    queue = Queue()

    # Add the start_node to the queue and visited list
    queue.put(start_node)
    visited.add(start_node)
    
    # start_node has not parents
    parent = dict()
    parent[start_node] = None

    # Perform step 3
    path_found = False
    while not queue.empty():
        current_node = queue.get()
        if current_node == target_node:
            path_found = True
            break

        for next_node in adj_list[current_node]:
            if next_node not in visited:
                queue.put(next_node)
                parent[next_node] = current_node
                visited.add(next_node)
                
    # Path reconstruction
    path = []
    if path_found:
        path.append(target_node)
        while parent[target_node] is not None:
            path.append(parent[target_node]) 
            target_node = parent[target_node]
        path.reverse()
    return path

graph = {
  1 : [2, 3, 4, 5],
  2 : [1, 3],
  3 : [1, 2, 4, 6],
  4 : [1, 3, 5, 6],
  5 : [1, 4, 6],
  6 : [3, 4, 5]
}

How can i modify this algorithm for my problem?



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source