Floyd算法

每对顶点间的最短路径——弗洛伊德（Floyd）算法 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的最短路径长度。

//////////////////////////////////////////////////////////////////////////////////// //用Floyd算法求每对顶点间的最短路径 #include

#include using namespace std;

#define vex 3//定义结点的个数

#define max 10000//设定一个极大值 void main()

{

int D[vex][vex][vex];//定义一个三维数组，用来一次一次的迭代，按FLOYD算法求出结点之间的最短路径

int arcs[vex][vex]={0,4,11,6,0,2,3,max,0};//邻接矩阵 int i,j,k;

for(i=0;ifor(j=0;jD[-1][i][j]=arcs[i][j];//为了使下边算法顺利进行，对数组之前内存空间进行初始化 for(k=0;kif(D[k-1][i][j]else

D[k][i][j]=D[k-1][i][k]+D[k-1][k][j];//求出每次迭代最小值，最后一次即为两个顶点之间的最短路径

//打印邻接矩阵

cout<<\"邻接矩阵：\"<for(j=0;j//打印最短路径

cout<for(j=0;jcout<