在Dijkstra算法中解决了单源点的最短路径问题，而Floyd(弗洛伊德算法)算法是用来解决多源点的最短路径问题。
算法思路：
Floyd算法基于动态规划的思想；假设v[i]到v[j]的最短路径中间经过前k(v[1], v[2], ..., v[k])的节点，现在我们把k+1，那么v[i]到v[j]的最短路径会有如下两种情况：
最短路径不变，说明最短路径没有经过v[k+1]。
最短路径发生了变化，说明最短路径必然经过v[k+1]，于是我们可以把新的最短路径分成两部分：v[i]->v[k+1]，和v[k+1]->v[j]。这两部分分别都满足：v[i]到v[k+1]的最短路径，v[k+1]到v[j]的最短路径，并且中间经过的节点序号不超过k。
可见在一条已知的最短路径上，其中任意两个节点的子路径也都是一条经过的中间节点不超过序号k的最短路径。
当k增加到n时，v[i]到v[j]就是要找的最短路径了。
所以我们把算法细化到如下步骤，要计算v[i]到v[j]的路径，进行n次试探：
初始计算v[i]到v[j]为：
如果v[i]和v[j]相通，则定义为v[i]到v[j]的边的权值。
反之，如果v[i]和v[j]不相通，则定义为无穷大(INF)。
下面考虑中间经过v[0]的路径，即v[i]->v[0]->v[j]，比较：
v[i]->v[j]和v[i]->v[0]->v[j]的路径长度，取较小者作为v[i]到v[j]的经过中间顶点序号不大于0的最短路径。
再考虑中间路径上增加顶点v[1]，即考虑路径v[i]->v[1]->v[j]，比较：
v[i]->v[j]和v[i]->v[1]->v[j]的路径长度，取较小者作为v[i]到v[j]的中间顶点序号不大于1的最短路径。
依次类推，直到中间经过顶点序号为n。
经过n次比较所有的中间节点，从而求得从v[i]到v[j]的最短路径。
算法实现：
这个算法实现非常简单，主题就是一个三重循环：
定义两个数组：
unsigned int dist[][]：用来记录v[i]到v[i]之间最短路径的长度。
unsigned int path[][]：用来记录v[i]到v[i]之间最短路径中v[i]后面紧跟着的那个节点序号。
注意在算法没有结束之前，这两个数组记录的都是中间值，不是最终值；只有当k=n这轮循环后，数组里的值才是最终的最短路径值。这和Dijkstra算法不一样，Dijkstra算法每计算出一个最短路径值就是其最终值。
#include <stdio.h>
int printpath(unsigned int path[][7], int from, int to) {
while (from != to) {
printf("%d->", from);
from = path[from][to];
}
printf("%d\n", from);
}
void floyd(unsigned int map[][7], int n) {
unsigned int dist[7][7];
unsigned int path[7][7];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = map[i][j];
path[i][j] = j;
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != -1 && dist[k][j] != -1 && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[i][k];
}
}
}
}
for (int to = 1; to < 7; to ++) {
int from = 0;
printf("dist[%d][%d]=%d,\tpath=", from, to, dist[from][to]); printpath(path, from, to);
}
}
int main() {
unsigned int map[][7] = {
0 1 2 3 4 5 6
---+-------------------------
*0*/{ 0, 13, 8, -1, 30, -1, 32},
*1*/{ -1, 0, -1, -1, -1, 9, 7},
*2*/{ -1, -1, 0, 5, -1, -1, -1},
*3*/{ -1, -1, -1, 0, 6, -1, -1},
*4*/{ -1, -1, -1, -1, 0, 2, -1},
*5*/{ -1, -1, -1, -1, -1, 0, 17},
*6*/{ -1, -1, -1, -1, -1, -1, 0},
/-----------------------------
};
floyd(map, 7);
}
算法就是一个三重循环，所以算法复杂度为O(n3)。
测试用例使用Dijkstra算法中的输入，并打印出从v[0]开始到其他节点的最短路径如下：
dist[0][1]=13, path=0->1
dist[0][2]=8, path=0->2
dist[0][3]=13, path=0->2->3
dist[0][4]=19, path=0->2->3->4
dist[0][5]=21, path=0->2->3->4->5
dist[0][6]=20, path=0->1->6
这个结果和使用Dijkstra算法是一样的；当然Floyd算法可以打印出任意两个节点的最短路径，不光是从v[0]开始。
k循环为什么放在外层
最后讨论一下循环问题，算法实现中我们看到在三重循环里面，k循环是在最外层的，为什么要在最外层呢，能不能放在最里层呢。
答案是：首先Folyd算法采用的是动态规划思想，动态规划思想要求针对一个变量的计算基于该变量的一个较小值的结果；比如，dist[k][i][j]表示节点v[i]和v[j]之间的中间节点序号不超过k时的最短路径，它是由dist[k-1][i][j]转换而来，即：
dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k]+dist[k-1][k][j])
我们看到计算dist[k][i][j]必须要先有dist[k-1][i][j]，dist[k-1][i][k]，以及dist[k-1][k][j]的结果值，展开来就是必须先有k-1时的dist数组的各个计算结果值dist[k-1][...][...]，所以k循环必须放在外面。即先计算出较小的k值时的状态，然后动态规划计算较大的k值时的状态。
举一个反向例子：如果k循环在最里层，当计算v[i]到v[j]的最短路径，假设循环k-1值已经完成，下面循环k值：
dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j]);
注意到此时dist[k-1][i][k]和dist[k-1][k][j])的值可能还没有计算出来，因为外层循环还在处理节点v[i]和v[j]，还没有处理v[i]到v[k]，v[k]到v[j]的最短路径，导致在使用dist[k-1][i][k]和dist[k-1][k][j]时，他们的值还不是中间节点序号不超过k-1的v[i]到v[k]和v[k]到v[j]的最短路径，从而计算出来的dist[k][i][j]是一个不正确的值。
