理解Dijkstra算法

作者: 桥头堡2015 | 来源:发表于2020-02-28 09:48 被阅读0次

    学习过最短路径问题的人都不会不知道Dijkstra算法。这个算法适用于解决无负权图的单源(且不管是否有向)最短路径问题。这篇小文来谈谈如何理解这一算法。

    这里首先给出一个Python 3的代码实现(以下代码出自Python Algorithms一书,略有改动)。

    from heapq import heappush, heappop
    
    
    def dijkstra(G, s):
        D, P, Q = {}, {}, [(0, None, s)]
        while Q:
            du, pu, u = heappop(Q)
            D[u], P[u] = du, pu
            for v in G[u]:
                if v not in D:
                    heappush(Q, (du + G[u][v], u, v))
        return D, P
    

    Dijkstra算法可以从很多角度去理解。我个人觉得最便于理解和记忆的角度,是将其视为一个图遍历算法。这从上面的代码中就能够看出来。遍历节点的算法都需要记录“前线”,也就是所有已经访问过但没有“完全考察”的节点。不同的遍历算法,记录“前线”所用的数据结构也不同。比如,BFS使用的是FIFO的队列,DFS可以使用FILO的栈;而上面的代码使用的则是一个优先队列。(实际上,如果待解决的图的所有边的权重都为同一正值的话,那么就可以用BFS来解决。换言之,BFS算法可以视为Dijkstra算法的一个特例,是可以用于(实际上是最佳的)解决无权图的单源最短路径的算法。)

    那么,怎么直观地去理解Dijkstra算法所表示的这一遍历过程呢?比如说,我们要解决的问题如果可以表现为下面这幅图——这是幅无向无负权图,其中S点表示起点,每条边的权重就是标注在旁边的数字——那么怎么去表现Dijkstra算法所设定的遍历呢?

    image

    这里需要耍一个思维上的小花招:我们把每条边想象成真实的路径,然后把权重想象成对应路径的长度。然后假设站在起点S的是旋涡鸣人。在0时刻,旋涡鸣人首先将起点S涂成黑色(在上面代码中表现为D[s], P[s] = 0, None),然后沿每条从S点出发的路径——在上图里就是SA、SB、SC三条边——派出一名影分身。这些影分身的速度都一样,每前进1个长度需花费1个单位的时间,所以在时刻7、9、14,这三个影分身分别依次到达C、B、A点。每个影分身到达自己的目的地时,都会检查该点有没有被涂黑;如果已经被涂黑,说明有别的影分身走了一条更短的路径来过这个点,那么这个后到的影分身就完成了自己的使命,不用再考察已被涂黑的点的后续节点,可以“噗”地一下化成青烟消失了;如果没有被涂黑,那么说明这个影分身走的是起点S到该点的最短路径,记下现在的时刻(也就是所循路径的长度,也即到S点的距离,D[u] = du)以及上一个节点(P[u] = pu),把这一点涂黑,最后朝每条未被涂黑的邻点派出新的影分身。例如上面的例子里,时刻9时,有一个从起点S出发的影分身会到达B点。由于B此时还是白色的,说明S到B的最短路径的长度为9。涂黑B点,然后朝A、E两点各派出一名影分身(之所以不往C点派影分身,是因为C点已经在时刻7被另一个从S点出发的影分身涂黑了,也就是已经在D这个dict里了)。注意从B点往A点出发的影分身将在时刻11(=9+2)到达,早于从S点出发往A点去的那个影分身(他将在时刻14到达),所以等后者到达时,会发现A点已经是黑色的了。如此重复,直到所有的影分身都消失了,也即所有从S点能够到达的点都涂成了黑色(遍历),也就是“前线”中不再有仍在路上的影分身(while Q不再继续)。这时候,所有被涂黑的点,都记录下了涂黑的时刻(最短距离)和每一个中间节点(最短路径)。

    按照这种理解,那么算法中的优先队列其实可以看作是时间轴。每次往优先队列里push一个元素,代表新派出一个影分身;而每次从优先队列里pop出一个元素,则代表了某个影分身到达了其目的节点。而且,这种思路还可以帮我们从直观上理解Dijkstra算法的适用范围:必须无负权边,因为影分身所走路径的长度不可能为负;既可以是有向图也可以是无向图,影分身按照允许的方向走就行了。

    以上就是我对Dijkstra算法的一点理解。希望能够对学习算法的同学有点帮助。

    相关文章

      网友评论

        本文标题:理解Dijkstra算法

        本文链接:https://www.haomeiwen.com/subject/ylhqhhtx.html