最短路径算法

网图中的最短路径：两顶点之间经过的边上权值之和最少的路径。

源点：路径上的第一个顶点

终点：路径上的最后一个顶点

 

迪杰斯特拉算法：

 

 

 算法流程：

1.定义final数组，当已求得V0到某顶点的最短路径，则该顶点在final数组的下标的值计为1。

 

2.初始化final数组和P数组，把它们所有元素的值全部初始化为0。

 

3.D数组存储第0行的数据：[0,1,5,65535,65535,65535,65535,65535,65535]，D[V0]=0，表示自己到自己的路径为零，因此final[0]=1，表示V0到V0的最短路径已求得。

final：[1,0,0,0,0,0,0,0,0]

 

4.从1开始循环：

定义变量min存储D[V0]的最小权值，变量k存储其下标。因此min=1，k=1，final[1]=1，final：[1,1,0,0,0,0,0,0,0]

 

如果V0到V1再到V1的邻接点的距离比直接从V0到该顶点的距离小，就该替换掉其在D数组中的值。替换后D：[0,1,4,8,6,65535,65535,65535]

 

P[]=k，则数组P[2]=1，P[3]=1，P[4]=1，P：

[0,0,1,1,1,0,0,0,0]，表示V0到V2、V3、V4的最短路径的前驱是顶点V1。

 

重新开始循环，因为final[0]=1，final[1]=1，所以V0和V1不参与循环。min=4，k=2，final[2]=1，final：[1,1,1,0,0,0,0,0,0]

 

如果V0到V2再到V2的邻接点的距离比直接从V0到该顶点的距离小，就该替换掉其在D数组中的值。替换后D为：[0,1,4,8,5,11,65535,65535,65535]

 

P[]=k，则数组P[4]=2，P[5]=2，P：

[0,0,1,1,2,2,0,0,0]，表示V0到V4、V5的最短路径的前驱是顶点V2。

 

循环结束后，final：[1,1,1,1,1,1,1,1,1]，表示找到了V0所有顶点的最短路径都找到了。

D：[0,1,4,7,5,8,10,12,16]，表示V0到各个顶点的最短路径的长度。

P：[0,0,1,4,2,4,3,6,7]，表示V0到各个顶点的最短路径的前驱，比如P[8]=7，P[7]=6，P[6]=3，P[3]=4，P[4]=2，P[2]=1，P[1]=0，则表示V0→V1→V2→V4→V3→V6→V7→V8

 

理解迪杰斯特拉算法：

每次遍历到离源点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

 

 

弗洛伊德算法：

 D-1代表顶点到顶点的最短路径长度的矩阵，P-1代表对应顶点的最小路径的前驱矩阵。

 

算法流程：

1.定义变量k代表中转顶点的下标，v代表起始顶点，k代表终止顶点。

 

2.当k等于0时，计算经过V0的路径是否比原两点路径长度更短，将当前两点权值设为更小的那个。由D-1得，经过0中转的路径没有更短的

 

2.当k=1，v=0时，k=2,3,4时，进V1中转的路径比从V0直接到V2,V3,V4的要短，还有v=2,3,4时也出现此情况，修改D-1，再把中转点的下标替换P-1中出现更改D-1的对应位置：

 

一直循环到k=8结束，最后D8，P8：

 求得D数组与迪杰斯特拉算法的D数组一样都是[0,1,4,7,5,8,10,12,16]，路径看P：从0到8，则P[0][8]=1，说明要经过V1，

P[1][8]=2，说明要经过V2，

P[2][8]=4，说明要经过V4，

P[4][8]=3，说明要经过V3……

最后得V0→V1→V2→V4→V3→V6→V7→V8

 

 

概括弗洛伊德算法：

初始化D和P之后，k从0开始，如果经过下标k的顶点的路径比原两点路径更短，则在D中修改原两点路径的值为经过下标为k的顶点的路径长度，再在P中把k赋给在D中修改过的对应位置的值。D中包含了最短路径长度的信息，P中包含了最短路径的信息。