Dijkstra 算法实现案例

好的，以下是一个使用 Dijkstra 算法实现最短路径查找的 Python 代码示例：

import heapq

def dijkstra(graph, start, end):
    # 初始化距离字典
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    # 初始化堆和访问过的集合
    pq = [(0, start)]
    visited = set()

    while pq:
        # 取出距离最小的顶点
        (current_distance, current_vertex) = heapq.heappop(pq)

        # 如果已经访问过，则跳过
        if current_vertex in visited:
            continue

        # 将当前顶点标记为已访问
        visited.add(current_vertex)

        # 如果已经到达终点，则直接返回最短路径距离
        if current_vertex == end:
            return distances[end]

        # 遍历当前顶点的所有邻居
        for neighbor, weight in graph[current_vertex].items():
            # 计算新的距离
            distance = current_distance + weight

            # 如果新距离更短，则更新距离字典和堆
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    # 如果无法到达终点，则返回 None
    return None

这个函数接受一个邻接字典 `graph`，表示图中每个顶点的邻居和权重；起点 `start` 和终点 `end`。它使用堆和距离字典来实现 Dijkstra 算法，最后返回起点到终点的最短路径距离，如果无法到达终点则返回 None。