//用迪杰斯特拉算法求單源點的最短路徑
#include<iostream.h>
const int max=32767;
const   int   n=5;      //max表示圖中頂點的個數
const int e=9;
struct   Graph
{  
int  arcs [n+1][n+1];           //圖的鄰接矩陣
int dist [n+1] ;                //存放從源點到各頂點的最短路徑
int path [n+1] ;             //存放在最短路徑上該頂點的前一頂點號
int s[n+1];                  //已求得的在最短路徑上的頂點的頂點號
}g;
void  shortestpath (const int Vl)     //Vl為源點
{for (int i=1;i<=n;i++)
{g.dist[i]=g.arcs[Vl][i];
g.s[i]=0;                         //已求出最短路徑上的頂點集合初始化
if ((i!=Vl)&&(g.dist[i]<max)) g.path[i]=Vl;
else  g.path[i]=0;
}
g.s[Vl]=1; g.dist[Vl]=0;
for (i=1; i<n; i++)
{ int min=max; int u=Vl;
for (int j=1; j<=n;j++)                       //求最短路徑
if (!g.s[j]&& g.dist[j]<min) {u=j,min=g.dist[j];}
g.s[u]=1;                                              // 將距離值最小的頂點并入集合S中
for(int w=1; w<=n; w++)              //修改路徑長度
if ((!g.s[w])&&(g.arcs[u][w]<max) &&(g.dist[u]+g.arcs[u][w]<
g.dist[w])) {g.dist[w]=g.dist[u]+g.arcs[u][w]; g.path[w]=u;} 
}
for (i=1;i<=n;i++)                    //輸出路徑長度及路徑
{if (i!=Vl)
{cout<<"最短距離為："<<g.dist[i]<<"   ";                             
cout<<"經過的頂點為："<<i;                                    //輸出終點
int pre=g.path[i];
while (pre!=0)
{cout<<"←"<<pre;
 pre=g.path[pre];
}
cout<<endl;
}
}
}
void main( )
{ int i,j,w,k;
  for(i=1;i<=n;i++)
	  for(j=1;j<=n;j++)
		  if(i==j) g.arcs[i][j]=0;
		  else g.arcs[i][j]=max;
	for(k=1;k<=e;k++)
    { cout<<"請輸入一條邊及權值:";
	  cin>>i>>j>>w;
	  cout<<endl;
	  g.arcs[i][j]=w;
	}
	cout<<"請輸入源點：";
	cin>>i;
	cout<<endl;
	cout<<"從"<<i<<"出發的最短路徑為"<<endl;
	shortestpath(i);
}