最短路径.cpp

校园导游咨询参考

#include<iostream.h>
#define OK 1
#define ERROR 0
#define INFINITY 255
#define MAX_VERTEX_NUM 20
typedef int Status;
typedef int ElemType;
typedef struct QNode{ElemType data; struct QNode *next;}QNode,*QueuePtr;
typedef struct{  QueuePtr front;QueuePtr rear;}LinkQueue;
    Status InitQueue(LinkQueue &Q)
    {
        Q.front=Q.rear=new QNode;
        if(!Q.front) 
        return ERROR;
        Q.front->next=NULL;
        return OK;
     }
   Status EnQueue(LinkQueue &Q,ElemType e)
   {
      QueuePtr p=NULL;
      p=new QNode;
      if(!p)
      return ERROR;
      p->data=e;
      p->next=NULL;
      Q.rear->next=p;
      Q.rear=p;
      return OK;
   }
   Status DeQueue(LinkQueue &Q,ElemType &e)
   {
      QueuePtr p=NULL;
      if(Q.front==Q.rear)
       return ERROR;
      p=Q.front->next;
     e=p->data;
     Q.front->next=p->next;
      if(Q.rear==p)     
      Q.rear=Q.front;
     delete p;
      return OK;
  }
   Status EmptyQueue(LinkQueue &Q)
   {
     return Q.front==Q.rear?true:false;
    }
    Status CopyQueue(LinkQueue &Q1,LinkQueue &Q2){
             int e;
             QueuePtr p;
            while(!EmptyQueue(Q2)){  
              DeQueue(Q2,e);
      }              
  p=Q1.front->next;
  while(p){
    e=p->data; p=p->next;  EnQueue(Q2,e);
       }
      return OK;
    } 
typedef struct ArcCell{
  int adj; char *info;       
     }AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
  char vexs[MAX_VERTEX_NUM][5];  
  AdjMatrix arcs;          
  int vexnum;            
  int arcnum;            
}MGraph;
Status createUDN(MGraph &G,int vexnum,int edgenum,char *names,char *edges,int key){
  int i,j,k,value;
  G.vexnum=vexnum;
  G.arcnum=edgenum;
  for(i=0;i<G.vexnum;++i){
    for(j=0;j<4;j++){
     G.vexs[i][j]=*names;
      names++;
    }
    G.vexs[i][4]='\0';
  }
  for(i=0;i<MAX_VERTEX_NUM;++i){
    for(j=0;j<MAX_VERTEX_NUM;++j){
      G.arcs[i][j].adj=INFINITY;
      G.arcs[i][j].info=NULL;
      
    }
  }
  for(k=0;k<G.arcnum;++k){
    i=int(*edges)-48;
    edges++;
    j=int(*edges)-48;
    edges++;
    value=(int(*edges)-48)*10;
    edges++;
    value+=int(*edges)-48;
    edges++;
    G.arcs[i][j].adj=value;
    if(!key){
      G.arcs[j][i].adj=value;
    }
  }
  return OK;
}
void PrintGraph(MGraph &G){
  int i,j;
  cout<<"\n//--------------- PrintMatrix -----------------//\n\n ";
  for(i=0;i<G.vexnum;++i){
    cout<<G.vexs[i]<<" ";
  }
  cout<<endl;
  for(i=0;i<G.vexnum;++i){
    cout<<"\n\n"<<G.vexs[i]<<" ";
    for(j=0;j<G.vexnum;++j){
      if(G.arcs[i][j].adj==INFINITY)
        cout<<" / ";
      else
        cout<<" "<<G.arcs[i][j].adj<<" ";
    }
  }
  cout<<"\n\n//--------------- PrintMatrix -----------------//\n\n\n\n";
}
void ShortestPath(MGraph &G,int v0){
  int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
  LinkQueue Q[MAX_VERTEX_NUM];
  for(i=0;i<G.vexnum;++i){
    InitQueue(Q[i]);
    D[i]=G.arcs[v0][i].adj;
    final[i]=false;
  }
  final[v0]=true;
  for(i=1;i<G.vexnum;++i){
    min=INFINITY;
    for(w=0;w<G.vexnum;++w){
      if(!final[w] && D[w]<min){
        v=w;
        min=D[w];
      }
    }
    final[v]=true;
    for(w=0;w<G.vexnum;++w){
      if(!final[w] && G.arcs[v][w].adj+min<D[w]){
        D[w]=G.arcs[v][w].adj+min;
        CopyQueue(Q[v],Q[w]);
        EnQueue(Q[w],v);
      }
    }
  }
  cout<<"//--------------- ShortestPath -----------------//\n\n";
  cout<<" 出发地->目的地\t最短距离\t详细路径\n\n";
  for(i=0;i<G.vexnum;i++){
    if(D[i]!=INFINITY){
      cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\t"<<D[i]<<" \t\t";
      cout<<G.vexs[v0];
      while(!EmptyQueue(Q[i])){
        DeQueue(Q[i],v);
        cout<<" -> "<<G.vexs[v];
      }
      cout<<" -> "<<G.vexs[i]<<endl;
    }else{
      cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\tNo path!\n";
      
    }
  }
  cout<<"\n//--------------- ShortestPath -----------------//\n\n\n";
}

void PrintCity(char *names,int vexnum){
  int i,j;
  cout<<"城市列表：\n\n";
  for(i=0;i<vexnum;++i){
    cout<<" "<<i<<"-";
    for(j=0;j<4;j++){
      cout<<*names; names++;
     }
    cout<<" ";
  }
  cout<<"\n请选择出发城市 >";
}


int main(){
  MGraph G;
  char *edges,*names;  int vexnum,arcnum,city,kind;
   vexnum=10;arcnum=14;
  names="宁波上海天津南京重庆北京深圳苏州云南杭州";
  edges="01440238036012202591186024503450575056406750604063509845";
  do{
    PrintCity(names,vexnum);
    cin>>city;
    cout<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－选择城市 3－退出\n\n请选择操作 >";
    do{
      cin>>kind;
      if(kind>=0 && kind <=3){
        createUDN(G,vexnum,arcnum,names,edges,kind%2);
        switch(kind/2){
        case 0:ShortestPath(G,city); break;
         case 1:PrintGraph(G); break;
         
        }
      }
      cout<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－选择城市 3－退出\n\n请选择操作 >";
    }
    while(kind<4);
  }
  while(kind<5);
}