我正在尝试将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')

回答：

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