最佳路由.cpp

运行应用本程序

#include<stdio.h>
#define maxlen 10
const int L=10000;
const int n=7;
int cost[n+1][n+1];//图的邻接矩阵，第0行第0列不用
int dist[n+1];
int source;
int set[n+1];
int record[n+1];//用来记录到达每个结点的最后一个结点序号
int path[n][n+1];//用来记录从源点到达每个结点的最短路径，0号单元用来记录路径上点的个数


void createGraph()
{typedef struct
{
  int a[maxlen],b[maxlen],w[maxlen];	/*第k边的起点，终点，权值*/
  char vexs[maxlen];                   /*顶点标志*/
  int arcs[maxlen][maxlen];            /*顶点数和边数*/
  int vexnum,arcnum;						 /*图的当前顶点数和弧数*/
} graph;
	graph g; 
int k;
	printf("请输入节点个数：");
	scanf("%d",&g.vexnum);
	printf("请输入三元组个数：");
	scanf("%d",&g.arcnum);
    
     for(k=1;k<=g.arcnum;k++)				/*输入所有边的信息*/
     {
       printf("\n 请输入第%d个三元组信息:",k);
       scanf("%d",&g.a[k]);
       scanf("%d",&g.b[k]);
       scanf("%d",&g.w[k]);
      }
int i,j,c=L;                          /*设c值999为无穷大*/
   for(i=0;i<=g.vexnum;i++)
	for(j=0;j<=g.vexnum;j++)
          cost[i][j]=c;	/*初始化邻接矩阵中的所有元素值为无穷大*/
   for (k=1;k<=g.arcnum;k++)
   {
    cost[g.a[k]][g.b[k]]=g.w[k];     /*对邻接矩阵赋值*/
      cost[g.b[k]][g.a[k]]=g.w[k];
   }
}





int findnode(int m){
   int i;
   for(i=1; i<=set[0]; i++)
	   if( set[i]==m )
		   return 1;
    return 0;

}


void findpath(){
	int k;
	int i;
	for(i=0; i<n; i++){
		if( i+1==source ){
			//若当前点为源点，则其代价为0，到达它的最后一点其本身
		   path[i][0]=1;
		   path[i][1]=source;
		}
				
		else{
          k=record[i+1];
		  path[i][0]=1;
		  while( k!=source ){
			  //将从源点到达第i+1点的路径反向保存
		     path[i][path[i][0]]=k;
			 k=record[k];
			 path[i][0]=path[i][0]+1;
		  }
		  //将源点也保存进来，此时path[i][0]中数目即为路径上结点数目
		  path[i][path[i][0]]=source;
		}
		
	}
}


void costinformation(){
   int i;
   int j;
   for(i=0; i<n; i++){
	   if( i+1==source )
		   printf("\n%d号结点为源点\n\n", source );
	   else{
		   
		   printf("从源点到%d号结点的最短路径为:\n",i+1);
		   for(j=path[i][0]; j>1; j--)
		     printf("(%d,%d)", path[i][j], path[i][j-1]);
			 printf("(%d,%d)", path[i][1], i+1);
		   printf("此最短路径的代价为:%d\n\n", dist[i+1]);
	   }
   }
}


void main(){
    int i;
	int t;
	int m;
	int p;
	set[0]=0;
	createGraph();
	printf("请输入源点:");
	scanf("%d", &source);
    for( i=1; i<=n; i++){
		//在给定源点后对dist,record两个数组进行初始化
		if( cost[source][i]!=L ){
			dist[i]=cost[source][i];
			record[i]=source;
		}
		else{
			dist[i]=L;
			record[i]=0;
		}
	}
     
	for(p=1; p<=n; p++){ 
       i=1;
       t=L;
      //找当前没有合并的点中距离最小的
	   while( i<=n ){
	   if( findnode(i)==0 ){
		   if(dist[i]<=t){
		     t=dist[i];
		     m=i;
		     i++;
		   }
		   else
			   i++;
	   }
	  else
		   i++;
   }

   
  //找到有最小距离的点，将其放入set集合
   set[set[0]+1]=m;
   set[0]=set[0]+1;
   
   //找到有最小距离的点，修改dist数组和record数组
   for(i=1; i<=n; i++){
	   if( dist[i] > dist[m]+cost[m][i] ){
	     dist[i]=dist[m]+cost[m][i];
		 record[i]=m;
	   }

   }

	}
	
	findpath();
	costinformation();
 scanf("%d",&source);
       printf("\n 请输入任意键");
scanf("%d",&source);
}