最短路径问题.txt

对一个运输商来说要把货运到收货地点选择最短的路线运输是其实现最大利润的要求

#include<iostream.h>
#include<iomanip.h>
#include<string.h>
const int M=999999;     //定义M为无穷大
const int maxvertexnum=100;    //预定的最大结点数
struct vertextype      {  char name[10];  int key;  };    //定义顶点元素类型
typedef vertextype vexlist[maxvertexnum]; //定义vexlist为存储结点信息的数组类型
typedef int adjmatrix[maxvertexnum][maxvertexnum];//定义adjmatrix为存储邻接距阵的数组类型
struct edgenode  {  int adjvex;int weight;edgenode *next;};  //定义邻接表中的边结点类型
typedef edgenode *adjlist[maxvertexnum];
//定义adjlist为存储maxvertexnum个表头指针的数组类型
int number, dist[maxvertexnum];
void createl(vexlist GV,adjmatrix GA)  //建立顶点数组GV，邻接数组GA
{  int i,j,k,w,edge,direction;
   cout<<"      *有向图用1表示，无向图用0表示*  "<<endl;
   cout<<"     ================================"<<endl;
   cout<<"             请选择:";
   cin>>direction;     cout<<"输入结点个数:";     cin>>number;
   cout<<"输入各结点:"<<endl;
   for(i=0;i<number;i++)            //建立顶点数组GV
		 {  cin>>GV[i].key>>GV[i].name;  }
   for(j=0;j<number;j++)
		 {  cout<<"用"<<GV[j].key<<"表示"<<GV[j].name<<"   "<<endl; }
   cout<<endl;
   for(i=0;i<number;i++)   //初始化邻接数组
		 {  for(j=0;j<number;j++)
			{  if(i==j)      GA[i][j]=0;  else  GA[i][j]=M;   }
		 }
   cout<<"输入边数:";        //建立邻接数组
   cin>>edge;     cout<<"输入各条边:"<<endl;
   for(k=0;k<edge;k++)
		 {  cin>>i>>j>>w;
	        if(direction==1)     GA[i][j]=w;   else   GA[i][j]=GA[j][i]=w;
		 }
   cout<<endl;    cout<<"输出邻接距阵:"<<endl;
   for(i=0;i<number;i++)
		 {  for(j=0;j<number;j++)
			 {  if(GA[i][j]==M)   cout<<setw(5)<<"∞";   
else  cout<<setw(5)<<GA[i][j];  
}
	        cout<<endl;
		 }
   cout<<endl;
}
void PATH(adjlist path,int m,int j);   //函数超前定义
void dijkstra(adjmatrix GA,int dist[],adjlist path,int i,int n)
//求图GA中从顶点i到其余每个顶点间的最短距离和最短路径它们分别被存
//于数组dist和path数组中
{  int j,k,w,m;
   int *s=new int[n];      //定义作为集合使用的动态数组s
   for(j=0;j<n;j++)        //分别给s,dist和path数组赋初值
		 {  if(j==i)   s[j]=1;   else    s[j]=0;
             dist[j]=GA[i][j];
             if(dist[j]<M&&j!=i)
			 {edgenode *p1=new edgenode;  edgenode *p2=new edgenode;
                p1->adjvex=i;  p2->adjvex=j;  p2->next=NULL;
                p1->next=p2;    path[j]=p1;
			}
           else    path[j]=NULL;
		}
for(k=1;k<=n-2;k++)  //共进行n-2次循环，每次求出从源点i到终点m的最短路径及长度
		{  w=M;m=i;        //求出第k个终点m
           for(j=0;j<n;j++)
           if(s[j]==0&&dist[j]<w)
			 {    w=dist[j];           m=j;   }
//若条件成立，则把顶点m并入集合s中，否则退出循环，因为剩余的顶点，
//其最短路径长度为M，无需再计算下去
          if(m!=i)   s[m]=1;   else   break;
          for(j=0;j<n;j++)//对s元素为0的对应dist和path中的元素做必要修改
          if(s[j]==0&&dist[m]+GA[m][j]<dist[j])
			{   dist[j]=dist[m]+GA[m][j];     PATH(path,m,j);
	//调用函数，由到顶点m的最短路径和顶点j构成到顶点j的目前最短路径
			}
		}
}
void PATH(adjlist path,int m,int j) //由到顶点m的最短路径和顶点j构成到顶点j的//目前最短路径
{   edgenode *p,*q,*s;         p=path[j];    //把顶点j的当前最短路径清除掉
    while(p!=NULL)
		{  path[j]=p->next;  delete p;  p=path[j];  }
    p=path[m];     //把到顶点m的最短路径拷贝过来到顶点j的最短路径上
    while(p!=NULL)
		{  q=new edgenode;  q->adjvex=p->adjvex;
            if(path[j]==NULL)   path[j]=q;
            else   s->next=q;   s=q;   p=p->next;
		}
//把顶点j加入到path[j]单链表的最后，形成新的目前最短路径
    q=new edgenode;   q->adjvex=j;  q->next=NULL;   s->next=q;
}
void main()
{ vexlist GV;  adjmatrix GA;
 createl(GV,GA);
vertextype again,from,to;      adjlist path;   int chose=1;   edgenode *p;
 while(chose!=0)           //为了实现多次查找
{ cout<<"      ********求城市之间的最短路径******* "<<endl;
    cout<<"       1、求一个城市到所有城市的最短路径 "<<endl;
    cout<<"       2、求任意的两个城市之间的最短路径 "<<endl;
    cout<<"      =================================== "<<endl;
    cout<<"         请选择：1 或 2，选择 0 退出 ：";
    cin>>chose;   cout<<endl;
    if(chose==1)    //求一个城市到所有城市的最短路径
      {  cout<<"输入源结点:";     cin/*>>again.key*/>>again.name;
         for(int num=0,node=0;node<number;node++)
	    if(strcmp(GV[node].name,again.name)==0)
	       {   again.key=GV[node].key; num++;   }
	    if(num)
            {  dijkstra(GA,dist,path,again.key,number);
               cout<<"查找结果:"<<endl;  cout<<endl;
               cout<<setw(32)<<"最短距离"<<setw(12)<<"最短路径"<<endl; 
               for(int i=0;i<number;i++)
	             { cout<<setw(10)<<GV[again.key].name<<"到"<<setiosflags(ios::left)
		             <<setw(10)<<GV[i].name<<resetiosflags(ios::left);
	               if(dist[i]==M)      cout<<setw(10)<<"∞"<<"    ";
	               else              cout<<setw(10)<<dist[i]<<"    ";
	               p=path[i];
	              if(again.key==i)     cout<<"目标在本地";
	              else
	                {   if(p!=NULL)
	                    { cout<<GV[again.key].name;    p=p->next;
		                 while(p!=NULL)
		                    { cout<<"→"<<GV[p->adjvex].name;   p=p->next;   }
	                    }
                         else   cout<<"不能到达!";
	                }
			     cout<<endl;
	             }
               cout<<endl;
	        }
	     else   cout<<"没有该查找信息"<<endl;
      }
   else if(chose==2)    //求任意的两个城市之间的最短路径
	 {  cout<<"输入起点："; 
         cin>>from.name;cout<<"输入终点：";cin>>to.name;
         for(int num1=0,num2=0,node=0;node<number;node++)
           {   if(strcmp(GV[node].name,from.name)==0)
	            {   from.key=GV[node].key;    num1++;   }
               if(strcmp(GV[node].name,to.name)==0)
	            {   to.key=GV[node].key;    num2++;  }
}
int num=num1+num2;
if(num)
{  dijkstra(GA,dist,path,from.key,number);
	          cout<<"最短路径为：";            p=path[to.key];
	          if(p!=NULL)
		        {  cout<<GV[from.key].name;      p=p->next;
		           while(p!=NULL)
		             {   cout<<"→"<<GV[p->adjvex].name;     p=p->next;   }
				  cout<<"      最短距离为:";
                     if(dist[to.key]==M)    cout<<"∞";
	                else                   cout<<dist[to.key]<<endl;
		        }
              else    cout<<"不能到达!"<<endl;
              cout<<endl;}else cout<<"没有该查找信息"<<endl;
           }
       else    cout<<"结束求最短路径，退出该程序，再见!"<<endl;
}
}