dDijkstra 算法

本文的目的仅仅是让人明白Dijkstra算法是怎么一回事，遇到图怎么使用，不作编码上的探讨。编码的我后面会再写一篇文章。
我们以一道2016年研究生计算机联考题为例：

首先创建一个数组dis，用来记录从1到其他节点的距离，第一次我们只看一条线的距离（虽然好比我们很容易看得出来1–3的最短距离是7），并记录。所以初始数组为
0 5 ∞ ∞ 4 ∞
第一个指就是1到1自己的距离，为0；第三个就是1到3的距离，说过了初始我们只看一条线的，所以还不到3，距离为∞。
那么可以确定，这张图从1到5的最短距离为4，因为即使你从2过，距离也有5，不可能比4小。1到2的距离为5，不一定是最短路径，如果4到2的距离小于1（虽然题目中显然不可能，但请务必看最小值），则1到2的距离会更短。
这里就可以记录第一趟选择的最短路径为1–5，距离为4。那么1–5的这个距离就是固定的了，可以在后面用的，我们也进行加粗，这个值不要再动了。
我们记录：第一趟，1–2距离为5；1–5距离为4，集合S为{1,5}

那么利用这1–5的距离，再多看一步，dis数组如下：
0 5 ∞ 11 4 9
由于我们可以利用1–5的距离，那就要看5的几个出度，5可以到2和6，那就分别记录1–5–2和1–5–6的距离，分别是11和9。
我们记录：第二趟，1–2距离为5；1–5–4距离为11；1–6距离为9，集合S为{1,5,2}（由于1–5的最小距离已经确定，就不用再做记录了）

这里同理，5是最小值（因为距离4我们已经固定了），我们就利用1到2的距离，看2的出度，并固定5，dis数组如下：
0 5 7 11 4 9
2只有一个出度，所以确定1–2–3的最短距离为7。
我们记录：第三趟，1–2–3距离为7；1–5–4距离为11；1–5–6距离为9，集合S为{1,5,2,3}

这里需要注意，最小数字为7，是1–3的距离，但是3的唯一出度为5，1–5我们已经确定了最短距离，所以我们固定这个7，但是不使用它。继续看9，是1–6，同理，6的出度是3也已经确定过距离，所以也只固定，不使用。
我们记录：第四趟，1–5–4距离为11；1–5–6距离为9，集合S为{1,5,2,3,6}

最后一步，就是确定了1–4的最短距离就是11。
我们记录：第五趟，1–5–4距离为11，集合S为{1,5,2,3,6,4}

答案表述上我们可能要把几趟的表述绘制成表格，这里我就直接放答案的图了

Originally published at https://www.flinty.moe on August 16, 2019.