搜索-查找到n个不同起始点的最近节点(统一成本)

import heapq

def ucs(graph, start, goal):
    frontier = []
    heapq.heappush(frontier, (0, start))
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while frontier:
        current_cost, current_node = heapq.heappop(frontier)

        if current_node == goal:
            break

        for next_node in graph[current_node]:
            new_cost = cost_so_far[current_node] + graph[current_node][next_node]
            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                cost_so_far[next_node] = new_cost
                priority = new_cost
                heapq.heappush(frontier, (priority, next_node))
                came_from[next_node] = current_node

    return came_from, cost_so_far

# 示例图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 5},
    'C': {'D': 1},
    'D': {}
}

came_from, cost_so_far = ucs(graph, 'A', 'D')
print("Path:", came_from)
print("Cost:", cost_so_far)