#include<iostream.h>
#include<iomanip.h>
#include<string.h>
const int M=999999;     //定義M為無窮大
const int maxvertexnum=100;    //預定的最大結點數(shù)
struct vertextype      {  char name[10];  int key;  };    //定義頂點元素類型
typedef vertextype vexlist[maxvertexnum]; //定義vexlist為存儲結點信息的數(shù)組類型
typedef int adjmatrix[maxvertexnum][maxvertexnum];//定義adjmatrix為存儲鄰接距陣的數(shù)組類型
struct edgenode  {  int adjvex;int weight;edgenode *next;};  //定義鄰接表中的邊結點類型
typedef edgenode *adjlist[maxvertexnum];
//定義adjlist為存儲maxvertexnum個表頭指針的數(shù)組類型
int number, dist[maxvertexnum];
void createl(vexlist GV,adjmatrix GA)  //建立頂點數(shù)組GV，鄰接數(shù)組GA
{  int i,j,k,w,edge,direction;
   cout<<"      *有向圖用1表示，無向圖用0表示*  "<<endl;
   cout<<"     ================================"<<endl;
   cout<<"             請選擇:";
   cin>>direction;     cout<<"輸入結點個數(shù):";     cin>>number;
   cout<<"輸入各結點:"<<endl;
   for(i=0;i<number;i++)            //建立頂點數(shù)組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++)   //初始化鄰接數(shù)組
		 {  for(j=0;j<number;j++)
			{  if(i==j)      GA[i][j]=0;  else  GA[i][j]=M;   }
		 }
   cout<<"輸入邊數(shù):";        //建立鄰接數(shù)組
   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);   //函數(shù)超前定義
void dijkstra(adjmatrix GA,int dist[],adjlist path,int i,int n)
//求圖GA中從頂點i到其余每個頂點間的最短距離和最短路徑它們分別被存
//于數(shù)組dist和path數(shù)組中
{  int j,k,w,m;
   int *s=new int[n];      //定義作為集合使用的動態(tài)數(shù)組s
   for(j=0;j<n;j++)        //分別給s,dist和path數(shù)組賦初值
		 {  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次循環(huán)，每次求出從源點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中，否則退出循環(huán)，因為剩余的頂點，
//其最短路徑長度為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);
	//調用函數(shù)，由到頂點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)           //為了實現(xiàn)多次查找
{ 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;
}
}