Dijkstra 算法

Created
May 31, 2020 4:01 PM

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

image

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