Image for post
Image for post

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

Image for post
Image for post

首先创建一个数组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}

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

Image for post
Image for post

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store