zuiduanlujing.cpp

数据结构最短路径

#include"iostream.h"
#include"stdlib.h"
#include "stdio.h" 
//定义最大的顶点数目
#define MAXPOINT 100
#define limit  32767   //设置没有路径的权代替无穷大
struct record{          //没个顶点的数据结构设置为一个数组队列
int number;  //顶点号
int flag;    //标志是否从队列中被选过如果为1表示选过为0表示未选
int allpath;  //从源点到这个点的当前最短距离（权最小）
}path[MAXPOINT+1];
	
   

  

void main()
{
printf("==============================================================\n");
printf("                 键入1回车，求最短路径\n");
printf("                 键入2回车，退出程序\n");
printf("                 32767表示无穷大\n\n");
printf("==============================================================\n");

do{ int m;char nn;
 scanf("%d",&m);scanf("%c",&nn);
if(m==1){	
  int n,e,k;
printf("输入顶点数(n)和边数(e):");
scanf("%d,%d",&n,&e);

int cost[MAXPOINT+1][MAXPOINT+1]; //用来表示图的邻接矩阵	
 int  i,j,temp,front=1,rear=MAXPOINT,N,minnumber;
//temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾
//N 表示待输入的源点号码 minnumber 表示选中的点的号码
int  min=32768;           //设置一个初始值
       for(i=0;i<=n;i++)
              for(j=0;j<=n;j++)
                      cost[i][j]=limit;
        
printf("请把各顶点用数字表示为：");
for(i=1;i<=n;i++)printf("%d ",i);
printf("\n\n");
printf("下面开始输入每条边的起点和终点，以及该边的权\n");
for(k=1;k<=e;k++) 
{  int m1=0,n1=0,l=0;
	printf("第%d条边=>",k);
     printf("   起点:");
     scanf("%d",&m1);        
       printf("  终点:");
	   scanf("%d",&n1);
printf("  权值:");
scanf("%d",&l);
cost[m1][n1]=l;
}      

//cout<<"请输入源点号"<<endl; //输入一个起点
//cin>>N;

for(N=n;N>=1;N--)//把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径

{ for(i=front;i<=rear;i++) //初始化每个点的信息
{if(i==N)
     path[i].allpath=0;
  else
   path[i].allpath=limit;
  path[i].flag=0;            
  path[i].number=i;
}

  while(rear>=1)    //控制循环次数
  {for(temp=front;temp<=n;temp++)
  {   if(path[temp].allpath<min&&path[temp].flag==0)//选出一个具有最值
//的点
      
  {  minnumber=path[temp].number; 
           min=path[temp].allpath ;
  }
        
  }
   min=32768;

  path[minnumber].flag=1;//把选中的点的标志变量置1表示已经被选过避免选中

   for(i=1;i<=n;i++)//进行类似广度优先搜索，更新最短路径
   {if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<path[i].allpath))
      path[i].allpath=path[minnumber].allpath+cost[minnumber][i];
   }

   rear--;//次数减1
  }
rear=n; //恢复数组以便于下一点的循环

 
for(j=1;j<=n;j++)
{
cout<<"第"<<N<<"点到第"<<j<<"点的最短路径长度（权）为";
cout<<path[j].allpath <<endl;
}

}

printf("\n   完毕\n"); 
printf("==============================================================\n");
printf("                 键入1回车，求最短路径\n");
printf("                 键入2回车，退出程序\n");
printf("==============================================================\n");
}

else if(m==2)break;
else printf("错误命令！请按说明重新输入\n");

}while(1);



}