算法十：多源最短路径（任意两点最短路径）之Floyd-Warshall算法
任意两点最短路径被称为多源最短路径，即给定任意两个点，一个出发点，一个到达点，求这两个点的之间的最短路径，就是任意两点最短路径问题，多源最短路径，而Floyd-Warshall算法最简单，只有5行代码，即可解决这个问题。
比如三个城市，城市1，城市2，城市3。从城市1到城市3需要10公里，从城市1到城市2需要3公里，从城市2到城市3需要4公里，如下图：
那么从城市1到城市3，如何走更近？1到3是直达，但是却10公里，而1到2到3，虽然转一下，但是距离短了，只要7公里。
这就引出了我们的观念，一个点到另一个点要变短，就要引入第三个点，甚至第四个点，第五个点。
假设在map数组里存储了点i到点j的距离map[i][j]，那么我们引入第三个点k，则如果点i到点j的距离比点i到点k加点k到点j，则点i到点j的最短距离是点i到点k加点k到点j。
即如果map[i][j]<map[i][k]+map[k][j]，则map[i][j]＝map[i][k]+map[k][j]
这就是Floyd-Warshall算法。核心代码如下：
//只能从k中转
for(k=1; k<=cityCount; k++){
//从i出发
for(i=1; i<=cityCount; i++){
//到j结束
for(j=1; j<=cityCount; j++){
if(map[i][j] > (map[i][k] + map[k][j])){
map[i][j] = map[i][k]+ map[k][j];
}
}
}
}
三个for循环，加一个if，加一个赋值，简简单单的五行代码，就实现了任意一个点到任意另一个点的最短距离。
显而易见，时间复杂度是O(n3).
完整代码如下
#include <stdio.h>
int map[11][11] = {{0}};
int book[11] = {0};
int main(){
int i, j, k, cityCount, roadCount, length, x, y;
scanf("%d %d", &cityCount, &roadCount);
for(i=1; i<=cityCount; i++){
for(j=1; j<=cityCount; j++){
map[i][j] = 0;
}
}
for(i=1; i<=roadCount; i++){
scanf("%d %d %d", &x, &y, &length);
map[x][y] = length;
}
//只能从k中转
for(k=1; k<=cityCount; k++){
//从i出发
for(i=1; i<=cityCount; i++){
//到j结束
for(j=1; j<=cityCount; j++){
if(map[i][j] == 0 || map[i][k] == 0 || map[k][j] == 0) continue;
if(map[i][j] > (map[i][k] + map[k][j])){
map[i][j] = map[i][k]+ map[k][j];
}
}
}
}
//现在的map里就是从一个点i到另一个点j的最短距离map[i][j]
printf("点1到点5的最短路径是：%d", map[1][5]);
}
输入
5 8
1 2 3
1 3 2
1 5 10
2 3 1
3 5 3
3 4 5
4 5 1
2 4 8
输入，5