最短路径之Dijkstra算法

男娘i 2022-05-27 10:47 263阅读 0赞

最短路径之Dijkstra算法(看到i,j,k三个变量可以理解为需要三个for循环，方便记忆)

本节来学习指定一个点(源点)到其余各个顶点的最短路径,也称为”单源最短路径”。与上篇的Floyed-Warshall算法一样，这里仍然使用二维数组a来存储顶点之间边的关系。如图:(假设我要求的是1号顶点到其余顶点的最短距离)   
![这里写图片描述][SouthEast]  
当然，我们还需要一个dis数组来存储1号顶点到其余顶点的当前距离，如图:   
![这里写图片描述][SouthEast 1]   
既然是求1号顶点到其余顶点的最短的距离,那么我们就从dis数组中找到一个距离1号顶点的最短距离的顶点。通过dis数组可知，当前距离一号顶点的最短的顶点为2号顶点。所以1号顶点到2号顶点的最短距离为2。为什么呢?因为距离都为整数，所以不可能找到第三个中转点使得1号顶点到2号顶点的距离最短了。只要从1号顶点到中转点，那么他们间的距离已经大于1号到2号顶点的距离了！(值得我们注意的是:并不是说之后只要从dis数组中找到最短的距离，那么就是1号顶点到该点的最短距离了)   
当前我们找到了1号顶点到2号顶点的最短距离为2，那么我们来看看2号顶点有哪些出边呢?由邻接矩阵我们可以知道,2号顶点的出边为3号和4号顶点,我们看看2—->3号这条边能否比直接从1—->3的距离变短呢?也就是说我们来比较dis\[3\]和a\[2\]\[3\]+dis\[2\]谁大谁小。可以知道a\[2\]\[3\]+dis\[2\]小于dis\[3\]所以我们更新当前1号到3号的距离，为5，同理，我们知道1—>4号的距离也可以缩小到8,所以，dis的数组变为:   
![这里写图片描述][SouthEast 2]

然后,我们继续找当前dis数组(除了2号顶点，因为我们已经找过了，所以在代码部分我们可以用一个数组来标记哪些点被找过了)距离1号顶点最短距离的顶点为5号顶点。然后我们看5号顶点有哪些出边，能否使得通过5号顶点使得某些点的距离变得更短。可以知道通过5号顶点可以使得1—>4号的距离缩短为5,1—->6号顶点的距离缩短为7。所以dis数组变为:   
![这里写图片描述][SouthEast 3]   
（5号顶点被用过了，我们就标记5号顶点）   
接下里我们从3，4,6号顶点找距离1号顶点最短的距离,当前为4号顶点,出边为4—>3,4—->6,没找到可以缩短的   
![这里写图片描述][SouthEast 3]   
继续从3,6找当前距离1号顶点最短的点为3，找3的出边，3—>5，dis\[5\]>a\[3\]\[5\]+dis\[3\]，没法缩短。   
![这里写图片描述][SouthEast 3]   
最后找到只剩下6这个顶点，没有出边。所以不dis不变   
![这里写图片描述][SouthEast 3]   
所以由dis数组可知，1号到1~6号的最短距离分别为，0,2,5,5,3,7

[SouthEast]: /images/20220527/4ff584597fc2490ca67ee63893bc1c8b.png
[SouthEast 1]: /images/20220527/d95e2a9473844bd7bdb815cf9bb6b009.png
[SouthEast 2]: /images/20220527/fd2ab15a8e934abfa1eb418685f20e43.png
[SouthEast 3]: /images/20220527/bc45016bfe474b3ba2219bd34371cda4.png