wzm_1017单源最短路径代码

Wzm_1017是一个常见的算法题目代号，通常与单源最短路径问题（Single Source Shortest Path, SSSP）有关。单源最短路径问题旨在寻找从给定图的一个顶点（即“源”）到其他所有顶点的最短路径。这个经典问题有两个著名的解决方案：迪杰斯特拉算法（Dijkstra's Algorithm）和贝尔曼-福特算法（Bellman-Ford Algorithm）。

迪杰斯特拉适用于边权重非负的情况，而贝尔曼-福特则可以处理边权重为负的情况，但效率较低。下面是一个简单的Python实现迪杰斯特拉算法的例子：

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        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(pq, (distance, neighbor))
                
    return distances

在这个例子中，`graph`是一个字典，其中键表示图中的节点，值是另一个字典，表示与该节点相邻的节点及其对应的边权。`start`是起点。