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

这里首先给出一个Python 3的代码实现（以下代码出自，略有改动）。

from heapq import heappush, heappopdef dijkstra(G, s):    D, P, Q, C = {s: 0}, {s: None}, [(0, s, None)], set()    while Q:        du, u, p = heappop(Q)        if u in C: continue        C.add(u)        D[u], P[u] = du, p        for v in G[u]:            if v not in C:                heappush(Q, (du + G[u][v], v, u))    return D, P

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

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

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

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

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