转自网页文章源自联网快讯-https://x1995.cn/1158.html
【1】最短路径文章源自联网快讯-https://x1995.cn/1158.html
最短路径？别乱想哈，其实就是字面意思，一个带边值的图中从某一个顶点到另外一个顶点的最短路径。文章源自联网快讯-https://x1995.cn/1158.html
官方定义：对于内网图而言，最短路径是指两顶点之间经过的边上权值之和最小的路径。文章源自联网快讯-https://x1995.cn/1158.html
并且我们称路径上的第一个顶点为源点，最后一个顶点为终点。文章源自联网快讯-https://x1995.cn/1158.html
由于非内网图没有边上的权值，所谓的最短路径其实是指两顶点之间经过的边数最少的路径。文章源自联网快讯-https://x1995.cn/1158.html
别废话了！整点实际的哈，你能很快计算出下图中由源点V0到终点V8的最短路径吗？文章源自联网快讯-https://x1995.cn/1158.html
文章源自联网快讯-https://x1995.cn/1158.html
【2】迪杰斯特拉算法文章源自联网快讯-https://x1995.cn/1158.html
迪杰斯特拉算法是按路径长度递增的次序产生最短路径的思路求解。文章源自联网快讯-https://x1995.cn/1158.html
具体算法及其详细讲解如下：文章源自联网快讯-https://x1995.cn/1158.html
文章源自联网快讯-https://x1995.cn/1158.html
阅读程序前，先要搞明白几个数组作用：文章源自联网快讯-https://x1995.cn/1158.html
final[w]=1; 表示V0到Vw顶点已经有最短路径的结果文章源自联网快讯-https://x1995.cn/1158.html
ShortPathTable[w]; 表示V0到Vw顶点的最短路径权值和文章源自联网快讯-https://x1995.cn/1158.html
Pathmatirx[w]; 表示V0到Vw顶点的前驱顶点下标值文章源自联网快讯-https://x1995.cn/1158.html
开始调用算法前，我们需要为案例图创建邻接矩阵图，如下所示：文章源自联网快讯-https://x1995.cn/1158.html
文章源自联网快讯-https://x1995.cn/1158.html
（1）程序开始运行，final数组是为了标记V0到某顶点是否已经求得最短路径。文章源自联网快讯-https://x1995.cn/1158.html
如果V0到Vw已经有结果，那么final[w]=1;文章源自联网快讯-https://x1995.cn/1158.html
（2）第5~10行，是对数据初始化工作。 此时final数组均赋值为0，表示所有点均未求得最短路径。文章源自联网快讯-https://x1995.cn/1158.html
D数组为 {0,1,5,65515,65535,65535,65535,65535,65535}。因为V0与V1和V2的边权值为1和5。文章源自联网快讯-https://x1995.cn/1158.html
P数组全为0，表示目前没有路径。文章源自联网快讯-https://x1995.cn/1158.html
（3）第11行，表示V0至V0路径为0。文章源自联网快讯-https://x1995.cn/1158.html
第12行，表示V0点到V0点已经求得最短路径，因此final[0]=1。文章源自联网快讯-https://x1995.cn/1158.html
此时final数组为 {1,0,0,0,0,0,0,0,0}，此时整个初始化工作完成。文章源自联网快讯-https://x1995.cn/1158.html
（4）第13~33行为主循环，每次循环求得V0与一个顶点的最短路径。除去V0，因此索引从1开始。文章源自联网快讯-https://x1995.cn/1158.html
（5）第15~23行，先令min为65535的极大值，通过w控制循环，与D[w]比较找到最小值为min=1，同时确定k=1。文章源自联网快讯-https://x1995.cn/1158.html
（6）第24行，由k=1可知与V0最近的顶点是V1，并且由D[1]=1知道此时V0到V1的最短路径是1。文章源自联网快讯-https://x1995.cn/1158.html
因此再将对应的final[1]设置为1。此时final数组为 {1,1,0,0,0,0,0,0,0}文章源自联网快讯-https://x1995.cn/1158.html
（7）第25~32行是一循环，此循环甚为关键。文章源自联网快讯-https://x1995.cn/1158.html
它的目的是在刚才已经找到V0与V1的最短路径基础之上，对V1与其它顶点的边进行计算，得到V0与它们的当前最短距离，如图所示：文章源自联网快讯-https://x1995.cn/1158.html
文章源自联网快讯-https://x1995.cn/1158.html
因为min=1,所以D[2]=5不再是V0到V2的最短路径，现在D[2]=V0->V1->V2=min+3=4, D[3]=V0->V1->V3=min+7=8,文章源自联网快讯-https://x1995.cn/1158.html
D[4]=V0->V1->V4=min+5=6，于是D数组当前值为 {0,1,4,8,6,65535,65535,65535,65535}。文章源自联网快讯-https://x1995.cn/1158.html
而P[2]=1，P[3]=1，P[4]=1，其表示V0到V2，V3，V4点的最短路径它们的前驱均是V1。文章源自联网快讯-https://x1995.cn/1158.html
此时P数组为 {0,0,1,1,1,0,0,0,0}。文章源自联网快讯-https://x1995.cn/1158.html
（8）新一轮循环，此时i=2。第15~23行，对w循环，注意因为final[0]=1和final[1]=1，由第18行的！final[w]可知：文章源自联网快讯-https://x1995.cn/1158.html
V0与V1并不参与最小值的获取。通过循环比较，找到最小值min=4，k=2。文章源自联网快讯-https://x1995.cn/1158.html
（9）第24行，由k=2，表示已经求出V0到V2的最短路径，并且由D[2]=4知道最短路径距离为4。文章源自联网快讯-https://x1995.cn/1158.html
因此将V2对应的final[2]设置为1，此时final数组为 {1,1,1,0,0,0,0,0,0}。文章源自联网快讯-https://x1995.cn/1158.html
（10）第25~32行，在刚才已经找到V0与V2的最短路径的基础上，对V2与其它顶点的边进行计算，得到V0与它们的最短距离。文章源自联网快讯-https://x1995.cn/1158.html
如图所示：文章源自联网快讯-https://x1995.cn/1158.html
文章源自联网快讯-https://x1995.cn/1158.html
因为min=4，所以D[4]=6不再是V0到V4的最短距离，现在D[4]=V0->V2->V4=min+1=5，D[5]=V0->V2->V5=min+7=11。文章源自联网快讯-https://x1995.cn/1158.html
因此D数组当前值为 {0,1,4,8,5,11,65535,65535,65535,65535}。文章源自联网快讯-https://x1995.cn/1158.html
而原本P[4]=1，此时P[4]=2，P[5]=2，它表示的意思是V0到V4和V5的最短路径前驱均为V2。文章源自联网快讯-https://x1995.cn/1158.html
此时P数组为 {0,0,1,1,2,2,0,0,0}。文章源自联网快讯-https://x1995.cn/1158.html
（11）重新再开始一轮循环，此时i=3。第15~23行，通过对w循环比较找到最小值min=5，k=4。文章源自联网快讯-https://x1995.cn/1158.html
（12）第24行，由k=4表示已经求出V0到V4的最短路径，并且由D[4]=5知道最短路径距离为5。文章源自联网快讯-https://x1995.cn/1158.html
因此将V4对应的final[4]设置为1。此时final数组为 {1,1,1,0,1,0,0,0,0}。文章源自联网快讯-https://x1995.cn/1158.html
（13）第25~32行，对V4与其它顶点的边值进行计算，得到V0与它们的当前最短距离，如图所示：文章源自联网快讯-https://x1995.cn/1158.html
文章源自联网快讯-https://x1995.cn/1158.html
因为min=5，所以D[3]=8不再是V0到V3的最短路径，现在D[3]=V0->V4->V3=min+2=7，同理：文章源自联网快讯-https://x1995.cn/1158.html
D[5]=V0->V4->V5=min+3=8，D[6]=V0->V4->V6=min+6=11，文章源自联网快讯-https://x1995.cn/1158.html
D[7]=V0->V4->V7=min+9=14，因此，D数组当前值为 {0,1,4,7,5,8,11,14,65535}。文章源自联网快讯-https://x1995.cn/1158.html
而原本P[3]=1，此时P[3]=4，原本P[5]=2，此时P[5]=4。文章源自联网快讯-https://x1995.cn/1158.html
另外P[6]，P[7]=4，它表示V0到V3，V5，V6，V7点的最短路径它们的前驱是V4。文章源自联网快讯-https://x1995.cn/1158.html
此时P数组值为 {0,0,1,4,2,4,4,4,0}。文章源自联网快讯-https://x1995.cn/1158.html
（14）之后的循环完全类似。得到最终的结果，如图所示：文章源自联网快讯-https://x1995.cn/1158.html
文章源自联网快讯-https://x1995.cn/1158.html
此时final数组为 {1,1,1,1,1,1,1,1,1}，它表示所有的顶点均完成了最短路径的查找工作。文章源自联网快讯-https://x1995.cn/1158.html
此时D数组为 {0,1,4,7,5,8,10,12,16}，它表示V0到各个顶点的最短路径数，比如D[8]=1+3+1+2+3+2+4=16。文章源自联网快讯-https://x1995.cn/1158.html
此时的P数组为 {0,0,1,4,2,4,3,6,7}：文章源自联网快讯-https://x1995.cn/1158.html
这个P数组值可能难理解一些。比如P[8]=7，它表示要查看V0到V8的最短路径时，顶点V8的前驱是V7；文章源自联网快讯-https://x1995.cn/1158.html
再由P[7]=6表示要查看V0到V7的最短路径时，顶点V7的前驱是V6，同理，P[6]=3表示V6的前驱是V3。文章源自联网快讯-https://x1995.cn/1158.html
这样就可以得到：V0到V8最短路径为V8<-V7<-V6<-V3<-V4<-V2<-V1<-V0文章源自联网快讯-https://x1995.cn/1158.html
即就是： V0->V1->V2->V4->V3->V6->V7->V8。文章源自联网快讯-https://x1995.cn/1158.html
评论