迪杰斯特拉算法——最短路径算法python

迪杰斯特拉算法是一种解决有向图中最短路径问题的算法。下面是使用Python实现迪杰斯特拉算法的步骤：

1. 创建一个空的字典dist，用于存储每个顶点到源点的距离，初始值为无穷大。
2. 将源点的距离设置为0，并将源点加入到一个集合visited中。
3. 对于源点的每个邻居，更新其距离为源点到该邻居的距离，并将其加入到一个优先队列中。
4. 从优先队列中取出距离最小的顶点，将其加入到visited集合中，并更新其邻居的距离。
5. 重复步骤4，直到所有顶点都被加入到visited集合中。

下面是一个使用Python实现迪杰斯特拉算法的例子：

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    visited = set()
    pq = [(0, start)]

    while pq:
        (d, u) = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)

        for v, w in graph[u].items():
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

其中，graph是一个字典，表示有向图的邻接表。例如，如果有一条从顶点A到顶点B的边权为3的边，则graph[A][B] = 3。start是源点的名称。函数返回一个字典，表示每个顶点到源点的最短距离。