考研专业课数据结构中Floyd（佛洛伊德）算法相关问题解析

在数据结构的图这一章，为了求最短路径，往往采用两种方法，一种是Dijkstra算法，一种就是Floyd算法。

Floyd算法是为了求所有顶点之间的最短路径问题，（~~太长可以不看~~）其基本思想是（严版教材）：

假设求从顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径（Vi，V0, Vj）是否存在（既判别弧（Vi，V0）和（V0, Vj）是否存在）。如果存在，则比较（Vi，Vj）和（Vi，V0, Vj）的路径长度取长度较短者为从Vi到Vj的的中间顶点的序号不大于0的最短路径。

假如在路径上再增加一个顶点V1，也就是说，如果（Vi，······，V1）和（V1，······，Vj）分别是当前找到的中间顶点的序号不大于0的最短路径。那么（Vi，······，V1，······，Vj）就有可能是从Vi到Vj的中间顶点的序号不大于1的最短路径，将他和已经得到的从Vi和Vj中间顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点V2，继续进行试探。

依次类推，在一般情况下，若（Vi，······，Vk）和（Vk，······，Vj）分别是从Vi到Vk和从Vk到Vj的中间顶点的序号不大于k-1的最短路径，则将（Vi，·······，Vk，······，Vj）和已经得到的从Vi和Vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从Vi到Vj的中间顶点的序号的序号不大于k的最短路径。

这样，在经过n次比较后，最后求得的必是从Vi和Vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。

大致思想是，在两个节点添加中间节点，看能不能将路径变短。

理解不了不要紧，我们用一个简单的例子来实际操作一下

总结一下：

1.求矩阵每个元素的值，比如求第二趟A²的A²[1][3],事实上是将A¹[1][2]与A¹[2][3]相加之后得到的值与原来的值A¹[1][3]比较，谁最小，就采用谁。推广，求Aⁿ[i][j](Aⁿ中第i行第j列的元素)，就是A(n-1)第i行第n列的元素A(n-1)[i][n] + A(n-1)第n行第j列的元素A(n-1)[n][j]的和与之前A(n-1)[i][j](A(n-1)中第i行第j列的元素)比较，谁小取谁。（因为结论2第一种情况，所以本结论可以直接用Aⁿ[i][n]+Aⁿ[n][j]来计算）

2.值不变的情况大致有两种，一是，求第几趟的运算结果，以该次数为行和列上的元素不变，直接照着抄下来即可，比如本题中，A²的A²[2][3]依然为1。

二是，通过结论1求出的值比原有值还要大，比如A²的A²[3[4],通过结论1求得值为6+7=13，比之前的4还要大，所以不变。