最短路径算法Dijkstra原理

Dijkstra算法是一种用于解决带权图的单源最短路径问题的贪心算法。该算法的基本思想是从起点开始，逐步扩大范围，直到覆盖所有顶点。具体来说，算法维护一个集合S，表示已经求出最短路径的顶点集合，以及一个数组dist，表示起点到各个顶点的距离。初始时，集合S为空，dist数组中除了起点为0，其余元素均为正无穷。每次从dist数组中选择一个距离最小的顶点u，将其加入集合S中，并更新与u相邻的顶点v的距离，即如果从起点到u的距离加上u到v的距离小于起点到v的距离，则更新dist[v]的值。重复执行该过程，直到集合S包含所有顶点为止。

以下是Dijkstra算法的Python实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离数组
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # 初始化堆
    heap = [(0, start)]
    # 开始迭代
    while heap:
        (d, u) = heapq.heappop(heap)
        # 如果当前顶点已经在集合S中，则跳过
        if d > dist[u]:
            continue
        # 遍历与当前顶点相邻的顶点
        for v, w in graph[u].items():
            # 如果从起点到v的距离大于从起点到u再到v的距离，则更新dist[v]的值
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

其中，graph是一个字典，表示图的邻接表，start是起点。