python最短路径问题

在Python中，解决最短路径问题的一种常见算法是Dijkstra算法。Dijkstra算法可以用于求解带权重的有向图或无向图中的最短路径。

以下是一个使用Dijkstra算法求解最短路径的示例代码：

import heapq

def dijkstra(graph, start):
    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].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# 示例图的邻接字典
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 2, 'B': 1, 'D': 1},
    'D': {'B': 3, 'C': 1, 'E': 4},
    'E': {'D': 4}
}

start_node = 'A'
distances = dijkstra(graph, start_node)

print(f"The shortest distances from node {start_node}:")
for node, distance in distances.items():
    print(f"To node {node}: {distance}")

在上述示例中，我们定义了一个`dijkstra`函数来实现Dijkstra算法。通过传入一个邻接字典表示的图和起始节点，我们可以得到从起始节点到其他节点的最短距离。这里使用了优先队列（堆）来实现最小堆的效果。

示例中的图是一个带权重的无向图，通过邻接字典的形式表示。然后，我们将起始节点设为'A'，并调用`dijkstra`函数来计算最短路径。最后，打印出从起始节点到其他节点的最短距离。

需要注意的是，如果图中存在负权边，则需要使用其他算法，如Bellman-Ford算法或SPFA算法来解决最短路径问题。以上代码仅适用于没有负权边的情况。