编写路线规划导航系统Dijkstra算法

好的，以下是Dijkstra算法的Python实现，实现的是有向图的单源最短路径问题，即给定一个起点和一个有向图，求从起点到所有其他节点的最短路径。

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，所有顶点距离起点为正无穷
    distances = {node: float('inf') for node in graph}
    # 起点距离为0
    distances[start] = 0
    # 初始化堆和visited字典
    heap = [(0, start)]
    visited = set()

    while heap:
        # 从堆中取出距离最小的顶点
        (cost, current_node) = heapq.heappop(heap)
        # 如果当前顶点已被访问过，跳过
        if current_node in visited:
            continue
        # 将当前顶点标记为已访问
        visited.add(current_node)
        # 遍历当前顶点的邻接点，更新距离字典和堆
        for neighbor, weight in graph[current_node].items():
            # 计算起点到邻接点的距离
            distance = cost + weight
            # 如果该邻接点已被访问过或当前距离比之前计算的距离更大，跳过
            if neighbor in visited or distance >= distances[neighbor]:
                continue
            # 更新距离字典和堆
            distances[neighbor] = distance
            heapq.heappush(heap, (distance, neighbor))

    return distances

上述代码中，graph是一个字典，表示有向图的邻接表，字典的键表示顶点，值是一个字典，表示该顶点的邻接点及其权重。start是起点顶点。

该函数返回一个字典，表示从起点到各个顶点的最短距离。