Dijkstra算法

Dijkstra算法使用了广度优先搜索解决赋权有向图(或无向图)的单源最短路径问题。

输入

该算法的输入包含了一个有权重的图G,以及G中的一个起点S,V是途中所有顶点的集合,E是图中所有顶点的集合。图中的边是两个顶点所形成的元素对,(u,v)表示顶点u到顶点v的边,w(u,v)表示这条边的权重。

输出

该算法能够在一个图中,找到从起点到任何其他顶点的最低权重路径(最短路径)。

流程

这个算法是通过为每个顶点v保留当前为止所找到的从s到v的最短路径来工作的。初始时,起点s的路径权重被赋为 0 (d[s]=0)。若对于顶点 m 存在能直接到达的边(s,m),则把d[m]设为w(s,m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。当算法结束时,d[v]中存储的便是从s到v的最短路径,如果路径不存在的话是无穷大。

边的拓展:如果存在一条从u到v的边,那么从s到v的最短路径可以通过将边(u,v)添加到从s到u的路径尾部来拓展一条从s到v的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比当前已知的d[v]的值要小,则可以用新值来替代当前d[v]中的值。拓展边的操作一直运行到所有的 d[v] 都代表从s到v的最短路径的长度值。此算法的组织令d[u]达到其最终值时,每条边(u,v)都只被拓展一次。

算法维护两个顶点集合S和Q。集合S保留所有已知最小d[v]值的顶点v,而集合Q则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从Q 移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中,算法对u的每条外接边(u, v)进行拓展。

伪代码

function Dijkstra(G, w, s)
for each vertex v in V[G]       // 初始化
    d[v] := infinity            // 将各点的已知最短距离先设成无穷大
    previous[v] := undefined    // 各点的已知最短路径上的前趋都未知
d[s] := 0                       // s到s的最小距离设为0
S := empty set
Q := set of all vertices
while Q is not an empty set
    u := Extract_Min(Q)
    S.append(u)
    for each edge outgoing from u as (u,v)
        if d[v] > d[u] + w(u,v)     // 拓展边(u,v)
            d[v] := d[u] + w(u,v)   // 更新路径长度到更小的那个和值
            previous[v] := u        // 纪录前趋顶点

为了记录最佳路径的轨迹,我们只需记录该路径上每个点的前趋,即可通过迭代来回溯出s到t的最短路径:

S := empty sequence 
u := t
while defined u                                        
    insert u to the beginning of S
    u := previous[u]      //previous数组即为上文中的p

发表评论

电子邮件地址不会被公开。 必填项已用*标注