求图最短路径的狄克斯特拉算法

狄克斯特拉算法（Dijkstra's Algorithm）是一种用于求解图中最短路径的算法。其基本思想是：从起点开始，每次选择当前距离起点最近的一个顶点，然后以该顶点为中心进行扩展，更新起点到其它顶点的距离。重复该过程，直到所有顶点都被标记为已确定的最短路径。

下面是狄克斯特拉算法的具体步骤：

1. 初始化：将起点标记为已确定的最短路径，其它顶点标记为未确定的最短路径。

2. 对于每个未确定的顶点，计算其与起点的距离，如果该距离小于当前已确定的最短路径，则更新该顶点的距离。

3. 从所有未确定的顶点中选择距离起点最近的一个顶点，将其标记为已确定的最短路径。

4. 重复步骤2和3，直到所有顶点都被标记为已确定的最短路径。

下面是狄克斯特拉算法的伪代码实现：

function Dijkstra(Graph, source):
    dist[source] ← 0
    for each vertex v in Graph:           
        if v ≠ source
            dist[v] ← infinity
            previous[v] ← undefined
        end if
        Q.add_with_priority(v, dist[v])
    end for 
    
    while Q is not empty: //主循环
        u ← Q.extract_min() 
        for each neighbor v of u: //对u的所有邻居v进行松弛操作
            alt ← dist[u] + length(u, v)
            if alt < dist[v]
                dist[v] ← alt
                previous[v] ← u
                Q.decrease_priority(v, alt)
            end if
        end for
    end while
    return dist[], previous[]
end function

其中，dist[]表示起点到各顶点的距离，previous[]表示各顶点在最短路径上的前驱节点，Q为一个优先队列，用于存储未确定的顶点和其对应的距离。