狄克斯特拉算法

节点与权重示意图

假设从起点到终点有多条路径可以选择，数字代表两个节点间路程的耗时，我们现在找出从起点到终点耗时最短的路径。

Step1： 我们从起点出发，统计到其他节点的耗时，由于未知到终点的耗时，设为无穷大：

节点	耗时
A	6
B	2
终点	∞

Step2： 因为B点是“更便宜”的节点，计算从起点经B点到达B点的相邻节点的耗时，如果有更低的耗时更新耗时表，如果耗时更长则保留原表：

节点	耗时
A	5
B	2
终点	7

可见：从 （起点→B点→A点） 的耗时为5，到达终点的耗时也有无穷大变为7，比原来的少，我们更新表格。

Step3： 重复刚才的过程，继续处理未处理的节点（这里是A点）：

节点	耗时
A	5
B	2
终点	6

我们发现经A点是无法到达B点的，这里我们保留原表格。

现在所有点处理完毕，容易得出耗时最短路程为：起点→B点→A点→终点（耗时6）。

---

上面例子能够容易看出所得的路径，但如果节点数量增加了，恐怕就不大容易，所以我们在表格中加入父节点。

Step1： 从起点出发，统计到其他节点的耗时

父节点	节点	耗时
起点	A	6
起点	B	2
暂无	终点	∞

Step2： 计算从起点经B点到达B点的相邻节点的耗时

父节点	节点	耗时
B	A	5
起点	B	2
B	终点	7

Step3： 重复刚才的过程，继续处理未处理的节点（这里是A点）

父节点	节点	耗时
B	A	5
起点	B	2
A	终点	6

利用父节点信息，我们自终点回溯得出耗时最短路程为：起点→B点→A点→终点（耗时6）。

总结一下，狄克斯特拉算法包含4个步骤：

• 1. 找出最“便宜节”点，即可在最短时间内到达的节点
• 2. 更新该节点邻居的开销，检查是否有前往它们的更短路径
• 3. 重复这个过程，对图中每个节点都这样做
• 4. 计算最终路径

---

节点与权重示意图

我们用上述方法，来计算一个更复杂的例子。

Step1： 计算起点相邻节点的耗时

父节点	节点	耗时
起点	A	5
起点	B	0
暂无	C	∞
暂无	D	∞
暂无	终点	∞

Step2： 计算从起点经过B点到达B点相邻节点耗时，如有更短耗时就更新

父节点	节点	耗时
起点	A	5
起点	B	0
B	C	30
B	D	35
暂无	终点	∞

Step3： 重复上一步，计算从起点经过A点到达A点相邻节点耗时，如有更短耗时就更新

父节点	节点	耗时
起点	A	5
起点	B	0
A	C	20
A	D	25
暂无	终点	∞

Step4： 现在我们看到与终点相邻节点中“最便宜”的是C点，我们计算C点的消耗

父节点	节点	耗时
起点	A	5
起点	B	0
A	C	20
A	D	25
C	终点	40

Step5： 重复上一步，计算D点的消耗

父节点	节点	耗时
起点	A	5
起点	B	0
A	C	20
A	D	25
D	终点	35

计算得耗时最短路劲为：起点→A点→D点→终点（耗时35）