l7_10.cpp

《数据结构（C++描述）》-李根强-源代码

//用弗洛伊德算法求所有顶点的最短路径
#include<iostream.h>
const int max=32767;
const   int   n=4;      //max表示图中顶点的个数
 const int e=8;
struct graph
{int  arcs[n+1][n+1];           //图的邻接矩阵
int a[n+1][n+1] ;                //存放从源点到各顶点的最短路径
int path[n+1][n+1] ;             //存放在最短路径上该顶点的前一顶点号
}g;
 int i,j,k;                    
void   floyd()   //用弗洛伊德算法求最短路径
{   for (int i=1;i<=n;i++)
   for (int j=1;j<=n; j++)
   { 
	   g.a[i][j]=g.arcs[i][j];
   if((i!=j)&&(g.a[i][j]<max))
	   g.path[i][j]=i;
   else  g.path[i][j]=0;
   }
   
for ( k=1; k<=n;k++)
for  (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if(g.a[i][k]+g.a[k][j]<g.a[i][j])
{g.a[i][j]=g.a[i][k]+g.a[k][j]; g.path[i][j]=g.path[k][j];
}
for (i=1;i<=n;i++)                  //输出路径长度及路径
for (j=1;j<=n;j++)
 if(i!=j)
{cout<<i<<"到"<<j<<"的最短距离为："<<g.a[i][j]<<"  " ;
int next=g.path[i][j];
cout<<"经过的顶点为："<<j;
    while (next!=i)
	{ cout<<"←"<<next;
    next=g.path[i][next];
	}
cout<<"←"<<i<<endl;
}
}

//44ddd//
void main( )
{ int i,j,w,k;
  for(i=1;i<=n;i++)
	  for(j=1;j<=n;j++)
		  if(i==j) g.arcs[i][j]=0;
		  else g.arcs[i][j]=max;
	for(k=1;k<=e;k++)
    { cout<<"请输入一条边及权值:";
	  cin>>i>>j>>w;
	  cout<<endl;
	  g.arcs[i][j]=w;
	}
	floyd( );
	
}