在python中将BFS转换为UCS(广度优先搜索为统一成本搜索)

Question

我正在尝试将python中的BFS程序转换为UCS(广度优先搜索到统一成本搜索(，但我很难为此制定逻辑我尝试过对图形进行排序，但无法使用我的逻辑完全应用UCS

如果有人能帮忙，也可以指导一下流程将如何工作，以及如何解决这个问题

import collections
graph = {
'A': [('B', 5), ('C', 7)],
'B': [('A', 5), ('D', 8), ('E', 1)],
'E': [('B', 1), ('D', 2)],
'D': [('B', 8), ('E', 2), ('F', 7), ('C', 2), ('I', 5)],
'F': [('D', 7)],
'I': [('D', 5), ('G', 14)],
'G': [('I', 14), ('C', 13)],
'C': [('A', 7), ('D', 2), ('G', 13)]}

def path_cost(path):
total_cost = 0
for (node, cost) in path:
total_cost += cost
return total_cost, path[-1][0]
def UCS(graph , startingnode ,goal):
#cost = 0
queue = [[(startingnode, 0)]]
visited = []
while queue:
for v in graph.values():
v.sort(key=lambda x: x[1])
print(graph.values())
node = queue[-1][0]
if node in visited:
continue
visited.append(node)
if node == goal:
return path
else:
adjacent_nodes = graph.get(node , [])
for (node2 , cost) in adjacent_nodes:
new_path = path.copy()
new_path.append([node2 , cost])
queue.append(new_path)

UCS(graph , 'A' , 'G')

Answer 1

graph = {
'A': [('B', 5), ('C', 7)],
'B': [('A', 5), ('D', 8), ('E', 1)],
'E': [('B', 1), ('D', 2)],
'D': [('B', 8), ('E', 2), ('F', 7), ('C', 2), ('I', 5)],
'F': [('D', 7)],
'I': [('D', 5), ('G', 14)],
'G': [('I', 14), ('C', 13)],
'C': [('A', 7), ('D', 2), ('G', 13)]}

def path_cost(path):
total_cost = 0
for (node, cost) in path:
total_cost += cost
return total_cost, path[-1][0]

def ucs(graph, start, goal):
queue = [[(start, 0)]]
visited = []
while queue:
queue.sort(key=path_cost)
path = queue.pop(0)
node = path[-1][0]
if node in visited:
continue
visited.append(node)
if node == goal:
print(path)
return path
else:
adjacent_nodes = graph.get(node, [])
for (node2, cost) in adjacent_nodes:
new_path = path.copy()
new_path.append([node2, cost])
queue.append(new_path)

ucs(graph, 'A', 'G')