Python实现Dijkstra算法：单源最短路径探索

Dijkstra算法是一种经典的图论算法，主要用于在带权有向图中寻找从一个特定源节点到其他所有节点的最短路径。它是一种贪心算法，通过逐步缩小目标集合，确保每一步都是局部最优的选择，从而达到全局最优的结果。Dijkstra算法的核心思想可以概括为以下步骤： 1. **初始化**： - 创建一个字典（或类似数据结构）来存储每个节点到起始节点的距离，初始时除了起始节点，其他所有节点的距离设置为无穷大。 - 将起始节点的距离设为0，将其加入优先队列（这里用最小堆实现），这样优先处理距离较小的节点。 2. **查找并更新**： - 使用优先队列（如Python中的`heapq`模块）按距离大小进行排序，每次取出距离最小的节点。 - 检查该节点是否已经访问过，如果已经更新过距离，则跳过。否则，遍历与该节点相连的所有邻居，计算经过当前节点后到达邻居的总权重。 3. **更新距离**： - 如果经过当前节点的新距离小于已知距离，就更新邻居节点的距离，并将这个更新过的节点及其新距离重新加入优先队列。 4. **重复过程**： - 继续这个过程，直到优先队列为空或者所有节点都被访问过，此时优先队列中的每个节点都包含了到起始节点的最短路径。 5. **返回结果**： - 最终得到的`distances`字典中存储了从起始节点到图中所有节点的最短路径长度。 在给定的C代码片段中，展示了如何使用链表结构（这里未提供，但通常Dijkstra算法使用邻接矩阵或邻接表表示图）来实现Dijkstra算法。C代码中可能涉及到结构体`Node`用于表示链表节点，但实际的链表部分并未给出。然而，根据提供的C语言框架，我们可以推测这部分代码会用来构建和操作图的结构以便进行算法的迭代。 在Python实现中，`graph`字典以邻接表的形式存储图，键是节点，值是另一个字典，其中键是邻居节点，值是边的权重。例如，一个无向图的邻接列表形式如下： ```python graph = { 'A': {'B': 1, 'C': 3}, 'B': {'A': 1, 'C': 2}, 'C': {'A': 3, 'B': 2} } ``` 这样，通过调用`dijkstra(graph, 'A')`，函数将返回从节点'A'到其他所有节点的最短路径长度。