'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 |
|---|
