6.4.2_3最短路径问题_Floyd算法

Floyd弗洛伊德

膜拜大佬，给大佬鞠躬鞠躬鞠躬。。。。。。。。。

Floyd算法 ----解决顶点间的最短路径：

过程：

如下：

初始化(没有中转点)：2个邻接矩阵A和path，第一个是没有中转点的2个顶点之间的最短路径(注意是2个顶点之间的直接路径，中间没有经过其他顶点，如果2个顶点比如A->B没有直接路径，A->C->B有路径，此时也写∞)，第2个是目前能找到的最短路径中2个顶点之间的中转点，刚开始没有中转点所以各2个顶点之间的中转点都设为-1

中转点加入V0顶点：在没有加入V0中转点时，A[2][1]即V2->V1路径长度根据A邻接矩阵知是∞，加入V0后即K=0，可以V2->V0,V0->V1，即A[2][0]+A[0][1]=5+6=11(根据A第一个邻接矩阵得出)得出加了中转点后V2->V1最短路径由∞变为11，则修改A[2][1]即第一个邻接矩阵V2->V1最短路径为11，修改第二个邻接矩阵V2->V1中转点为0，所有的顶点都需要加入以上判断，然后修改A和Path,目前看只有V2、V1顶点需要(A(0)[2][1]=11即加入了0号中转点的V2->V1的最短路径长度为11，path(0)[2][1]=0，即当前的V2->V1最短路径长度加入了0号中转点，每次都要判断未加入中转点的最小路径长度>加入了中转点之后的最小路径长度，只有满足这个式子才会修改A和Path)

中转点加入V1顶点：在没有加入V1中转点时，V0->V2路径长度是13，加入后V0->V1->V2即6+4=10，加入后值小满足规则条件A(0)[0][2]>A[0][0][1]+A(1)[1][2]，修改A(1)[0][2]=10，path(1)[0][2]=1,其他顶点无需更改，加入中转点后路径没有变化

中转点加入V2顶点：在没有加入V2中转点时，V1->V0路径长度是10，加入后V1->V2->V0即4+5=9，加入后值小满足规则条件A(1)[1][2]>A(1)[1][2]+A(1)[2][0]，修改A(2)[1][0]=9，path(2)[1][0]=2

path写的是中转点，把谁加入了中转点对应的path路径上的值就写谁，A写的是最短路径长度

经过n(顶点个数)轮中转之后得到A(n-1)path(n-1)

如下：由A(n-1)即A(2)得，V1->V2最短路径是4，由path(2)得V1->V2是-1，即V1->V2最短路径4没有经过中转点，即为V1->V2，V0->V2最短路径是10，由path(2)得V1->V2是1，即V0->V2最短路径10经过中转点1，即为V0->V1->V2即V0_V1_V2

代码如下： 

准备一个图的邻接矩阵A+path矩阵初始值都设为-1，开始每循环一次增加一个中转点，每增加一个中转点遍历一次A邻接矩阵(遍历行和列)，看加了中转点之后的路径长度和不加谁小，如果加了小更新邻接矩阵A最短路径长度和path中转点

时间复杂度:要根据顶点个数遍历3次即O(|V³|)

空间复杂度：矩阵的存储空间行和列即O(|V²|)

5个顶点例子：

中转点V0:没有需要更新的

中转点V1：既然是V1作为中间点出现，那必然要找指向V1的点作为起点V2和从V1指出的点(此时不要直接看图，要看邻接矩阵)V3、V4,可得V1作为中间点、V2作为起点有2条路径，V2->V1->V3=1+1=2，但是V2->V3没有直接路径即∞，修改A(1)[2][3]=2,path(1)[2][3]=1，另一条V2->V1->V4=1+5=6，V2直接到V4=7，则修改A(1)[2][4]=6,path(1)[2][4]=1【修改对应path上的横纵坐标确定的值为1】

中转点V2：既然是V2作为中间点出现，那必然要找指向V2的点作为起点V0和从V2指出的点(直接看邻接矩A中V2作为横坐标V2所在行有值的点，不要看图！！！)即V1、V3(V2->V3在图中并没有直接指向，但是在邻接矩阵A中(2,3)=2,是因为上一步已经加入了中转点V1，V2->V3没有直接路径，但是可以V2->V1->V3=2有中转点路径，即在使用中转点V2时也使用了中转点V1的结果，在已经有了一个中转点的情况下，计算某2个顶点最短路径时也要看邻接矩阵而不是看图上边的权值！！！)、V4,可得V2作为中间点、V0作为起点有3条路径，V0->V2->V1=1+1=2(邻接矩阵中V0->V2是1，V2->V1是1) <V0->V1是∞，修改A(2)[0][1]=2,path(2)[0][1]=2，另一条V0->V2->V4=1+6=8(注意不要看图上的权值，看邻接矩阵中的最短路径！！！否则就变成了1+7=8，邻接矩阵A上V0->V2=1,V2->V4=6即1+6=7)，V0直接到V4=10，则修改A(2)[0][4]=8,path(2)[0][4]=2，另一条V0->V2->V3=1+2=3(邻接矩阵A上V0->V2=1,V2->V3=2即1+2=3) < V0->V3=∞，则修改A(2)[0][3]=3,path(2)[0][3]=2【修改对应path上的横纵坐标确定的值为2】

中转点V3：上同

中转点V4：上同

根据最终中转矩阵找路径：

如下为最终中转的A和path，找V0->V4路径，由A知V0->V4最短路径为4，由path知V0->V4中转点是3，再由A知V3->V4最短路径1，由path知V3->V4=-1即V3和V4之间没有中转点，再看V0->V3，由A知V0->V3最短路径3，由path知V0->V3=2级V0->V3中转点V2，即V0->V2->V3，看V0->V2，由A知V0->V2最短路径1，由path知V0->V2=-1即V0->V2没有中转点，再看V2->V3，由A知V2->V3最短路径2，由path知V2->V3=1即V2->V3有中转点V1，即V2->V1->V3，看V2->V1，由A知V2->V1最短路径1，由path知V2->V1=-1即V2->V1没有中转点，再看V1->V3，由A知V1->V3最短路径1，由path知V1->V3=-1即V1->V3没有中转点

V0->V3->V4  第一轮   V3->V4不动路径为1，看V0->V3有哪些中转点

V0->V2->V3->V4第二轮  V0->V2不动路径1、V3->V4不动路径1，看V2->V3有哪些中转点

V0->V2->V1->V3->V4第三轮  V0->V2、V2->V1、V1->V3、V3->V4不动路径1，各路径无中转点

练习：

弗洛伊德算法可解决带负权值，但不能解决带回路的负权值

  

知识回顾：

 

下次再见