经过指定的中间节点集的最短路径算法python代码

下面是一个使用Dijkstra算法来寻找从起点到终点的最短路径的Python代码示例，其中经过了指定的中间节点集。

import heapq

def shortest_path(graph, start, end, nodes):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    
    path = []
    
    for node in nodes:
        if distances[node] == float('inf'):
            return None
        path.append(node)
    
    return path

# 示例图示
graph = {
    'A': [('B', 2), ('C', 5)],
    'B': [('A', 2), ('C', 2), ('D', 1)],
    'C': [('A', 5), ('B', 2), ('D', 3), ('E', 1)],
    'D': [('B', 1), ('C', 3), ('E', 1)],
    'E': [('C', 1), ('D', 1)]
}

start = 'A'
end = 'E'
nodes = ['B', 'C', 'D']

path = shortest_path(graph, start, end, nodes)

if path:
    print(f"Shortest path from {start} to {end} via {nodes}: {' -> '.join([start] + path + [end])}")
else:
    print("Path doesn't exist.")

该代码使用了一个字典来表示图，其中键是节点，值是该节点与其他节点的连接以及对应的权重。算法使用了一个优先队列来存储节点，以便按照距离的顺序进行处理。在算法的最后，将返回从起点到终点经过中间节点集的最短路径。如果路径不存在，则返回None。