多源最短路径floyd
算法
其实相当简单。
基本思想就是一个贪心法，构造1个二维矩阵进行迭代，时间复杂度为o(n^3)。
二维数组g[][]表示图上边的权（就是2个点之间的直接距离）
二维数组weight[][]是我们构造出来的二维矩阵，用来储存当前得到的最短路径。
首先，用g[][]来初始化weight[][]（把g里的数据copy到weight里）
接下来，遍历图中所有结点v
如果g[i][v]+g[v][j]<weight[i][j]
那么weight[i][j]=g[i][v]+g[v][j]
遍历完所有结点之后，weight里储存的就是每两个点之间的最短路径
证明过程就不写了，几乎每本算法书里都有的，而且我觉得也没什么必要
下面是c的实现
g[i][j]=0表示 i 到 j 无路径
void floyd(float **g,long n,float **weight)
{
long i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
weight[i][j]=g[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
{
if(g[i][k]==0)
continue;
for(j=0;j<n;j++)
{
if(g[k][j]==0)
continue;
if(weight[i][j]==0 ||
g[i][k]+g[k][j]<weight[i][j])
weight[i][j]=g[i][k]+g[k][j];
}
}
}
floyd算法
#include "iostream.h"
int min(int a,int b){ return a>b?b:a;}
int cost[10][10]={ 0, 99, 8, 7, 6, 5, 4, 3, 2, 1, 99, 0, 99, 8, 7, 6, 5, 4, 3, 2, 8, 99, 0, 99, 8, 7, 6, 5, 4, 3, 7, 8, 99, 0, 99, 8, 7, 6, 5, 4, 6, 7, 8, 99, 0, 99, 8, 7, 6, 5, 5, 6, 7, 8, 99, 0, 99, 8, 7, 6, 4, 5, 6, 7, 8, 99, 0, 99, 8, 7, 3, 4, 5, 6, 7, 8, 99, 0, 99, 8, 2, 3, 4, 5, 6, 7, 8, 99, 0, 99, 1, 2, 3, 4, 5, 6, 7, 8, 99, 0};int best[10][10];
void Floyd(int cost[10][10],int best[10][10]){ int i,j,k; for(i=0;i<10;i++) for(j=0;j<10;j++) best[i][j]=cost[i][j];
for(i=0;i<10;i++) for(j=0;j<10;j++) for(k=0;j<10;j++) { best[j][k]=min(best[j][k],best[i][j]+best[i][k]); }}
main(){ Floyd(cost,best); for(int i=0;i<10;i++) { for(int j=0;j<10;j++) cout<<best[i][j]<<" "; cout<<endl; }}
------------------------------------------------------------------------------------------------------------------------------------------
每对顶点间的最短路径——弗洛伊德（Floyd）算法
解决此问题有两种方法：其一是分别以图中每个顶点为源点共调用n次Dijkstra算法；其二是采用
Floyd算法。两种算法的时间复杂度均为O(n3)，但后者形式上比较简单。
Floyd算法的基本思想：
（1）利用二维数组A[1..n-1][1..n-1], A[i][j]记录当前vi到vj的最短路径长度，数组A的初值等于图的代权临街矩阵;
（2）集合S记录当前允许的中间顶点，初值S=Φ;
（3）依次向S中加入v0 ,v1… vn-1，每加入一个顶点，对A[i][j]进行一次修正：设S={v0 ,v1… vk-1}，加入vk，则A(k)[i][j] = min{ A(k-1)[i][j]，A(k-1)[i][k]+A(k-1)[k][j]}。
A(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。
A(n-1)[i][j]就是vi到vj的最短路径长度。
