17、求任意两个节点之间最短距离——Floyd算法
Floyd算法：给出一个图(通常可以在任何图中使用，包括有向图、带负权边的图)，求最短路径问题的一个O(n^3)算法。
优点：容易理解，可以算出任意两个节点之间最短距离的算法，程序容易写;
缺点：复杂度达到三次方，不适合计算大量数据;
它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。注意单独一条边的路径也不一定是最佳路径。
Floyd-Warshall算法的基本思路是：
1.用d[i][j]记录每对顶点间的最短距离;
2.对每一个图中的顶点，以其作为基点扫描每一对d[i][j]，检验是否通过该基点可以使得这对顶点间的距离变小。
//dist(i,j) 为从节点i到节点j的最短距离
Fori←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)
Fork←1 to n do // k为“媒介节点”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j))then // 是否是更短的路径?
dist(i,j) = dist(i,k) + dist(k,j)
我们实际是很容易就可以写出这个算法的代码：
#defineN 100
voidFloyd(int dist[N][N],int n)
{
int i,j,k;
for(k=0;k
for(i=0;i
for(j=0;j
if(dist[i][k]+dist[k][j]
dist[i][j]=dist[i][k]+dist[k][j];
}
即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许的话(只要有放的下邻接矩阵的空间，时间上就没问题)。
对上面的代码来说，我们还面临一个保存路径的问题，如何来做呢?
/*多源最短路径floyd_warshall算法*/
#defineN 100
intmap[N][N];
voidFloyd(int dist[N][N],int path[N][N],int n)
{
int i,j,k;
for(i=0;i
for(j=0;j
dist[i][j]=map[i][j], path[i][j]=0;
for(k=0;k
for(i=0;i
for(j=0;j
if(dist[i][k]+dist[k][j]
{
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
voidoutput(int i,int j)
{
if(i==j)
return;
if(path[i][j]==0)
cout<