Dijkstra算法

抽象定义

输入：加权图 $G=(V(G),E(G)),\ w:E(G)\rightarrow \mathbf{R}^+$，顶点 $u_0\in V(G)$

输出：$u_0$ 到其余所有顶点的最短路径和对应距离

集合S用来存储已经找到的最短路径，l记录路径终点的前导节点

1. 任给 $u,v\in V(G)$，若 $u,v\notin E(G)$，令 $w(uv)=\infty$
2. 令 $d(u_0)=0,\ l(u_0)=u_0$; 任给 $u \in V(G),\ u \neq u_0,\ d(u)=\infty,\quad l(u)=*$; $S_0=\left\{u_0\right\};\ i=0$
3. 对任给 $u\in V(G)-S_i$，若 $d(u_i)+w(u_iu)<d(u)$，则令 $d(u)=d(u_i)+w(u_iu),\ l(u)=u_i$
4. 选出 $u_{i+1}\in V(G)-S_i$，使得 $d(u_{i+1})=min_{u\in V(G)-S_i}d(u)$，令 $S_{i+1}=S_i\cup{u_{i+1}}$
5. 若 $i=v(G)-1$，算法停止；否则，i++，转(3)

通俗理解

其实是类似贪心加广搜加动归，大致思路是这样的：

先把内层的，最靠近起点的最短路径确定好，然后通过已知的最短路径做中继点，更新其外层节点的现有最短路径，这里的内外层其实是根据离起点的距离分的。就是说要到1000m外的一个地方，中间很多休息区，我要贪心地走每一步，即保证我一定是通过最短路径走到前导节点。到目标点的路径长度随着前导节点的变化不断变短，直至最短。

例题详解

例1：

第一层：从v1出发，计算v1到其它节点的距离（无法连接则用“无穷”符号）

全表找最小值，发现v1到v6最短为3

• S中添加一条最短路径：v1——v6
• v6列标红不再考虑

第二层：从v1——v6出发，计算v1通过v6到其它节点的距离

在全表中找最小值（v6列已经删除)，此时4为最小值，对应路径v1——v6——v5

• 添加最短路径v1——v6——v5
• v5列不再考虑

第三层：从v1——v6——v5出发，计算v1通过v6及v5到其它节点的距离

• 已知v1——v6——v5长度为4；

• 发现，v5不能到现存的其它任何一个节点，因此距离全部为“无穷”

• 看全表（v5和v6已经删除）找最小值，5是最小值，对应的路径是v1——v6——v2

• 添加最短路径v1——v6——v2
• v2列不再考虑

新最短路径：v1——v6——v2

第四轮：从v1——v6——v2出发，计算v1通过v6及v2到其它节点的距离

v1——v6——v2到其它现存节点的距离（v2，v5，v6已删除)

• 遍历全表（v2，v5和v6已经删除）发现，9最小，对应的路径为v1——v6——v4
• 添加最短路径v1——v6——v4
• v4列不再考虑

新最短路径：v1——v6——v4

第五轮：从v1——v6——v4出发，计算v1通过v6及v4到其它节点的距离

计算v1——v6——v4到其它节点的距离（只剩v3列)

• 遍历全表发现，12是现存的最小值，对应v1——v6——v2——v3路径最短
• 添加最短路径v1——v6——v2——v3
• v3列不再考虑

添加最后一条最短路径：v1——v6——v2——v3

• 由于全部列已经删除，因此结束遍历

最终的表格

每列的标红值，则为v1到该节点的最短距离；从S列中找结尾为该列的路径。

结果汇总

v1到各节点的路径及其最短距离

• v2：v1——v6——v2 = 5

• v3：v1——v6——v2——v3 = 12

• v4：v1——v6——v4 = 9
• v5：v1——v6——v5 = 4
• v6：v1——v6 = 3

例2：

参考文章：

【看完必懂】Dijkstra算法（附案例详解）- 知乎(zhihu.com)