简介：
算法的特点：
弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭 包。算法思想：
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。
假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。 接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成！
举个例子：已知下图，
如现在只允许经过1号顶点，求任意两点之间的最短路程，只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1~n循环，j也是1~n循环，代码实现如下。
for(i=1; i<=n; i++){ for(j=1; j<=n; j++) { if ( e[i][j] > e[i][1]+e[1][j] ) e[i][j] = e[i][1]+e[1][j]; }} 接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。
//经过1号顶点for(i=1; i<=n; i++) for(j=1; j<=n; j++) if (e[i][j] > e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j];//经过2号顶点for(i=1; i<=n; i++) for(j=1; j<=n; j++) if (e[i][j] > e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j];
最后允许通过所有顶点作为中转，代码如下：
for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];
这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。与上面相同
核心代码：
for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j];