/* 鄭章孝  學號：012002013324  班級：CS0201 */
#include<stdio.h>
#include <iostream.h>
#include<stdlib.h>
//Dijkstra算法的實現
const int max=1000;     				/*max代表一個很大的數*/
void dijkstra (int v,int **cost,int n)/*求源點v到其余頂點的最短路徑及其長度*/
{   int *s=new int[n],*pre=new int[n],*dist=new int[n];
	int i,min,j,k,p;
  for (i=0;i<n;i++)
    { dist[i]=cost[v][i]; /*初始化dist*/
      s[i]=0;            /*s數組初始化為空*/
      if (dist[i]<max)
        pre[i]=v;
      else pre[i]=0;
     }
  pre[v]=0;
  s[v]=1;      					/*將源點v歸入s集合*/
  for (i=0;i<n;i++)
   { min=max;
     for (j=0;j<n;j++)
        if (!s[j] && (dist[j]<min))
          { min=dist[j];
           k=j;
           }       				/*選擇dist值最小的頂點k+1*/
     s[k]=1;        				/*將頂點k+1歸入s集合中*/
     for (j=0;j<n;j++)
        if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
          { dist[j]=dist[k]+cost[k][j];    	/*修改 V-S集合中各頂點的dist值*/
            pre[j]=k+1;         		/*k+1頂點是j+1頂點的前驅*/
            }
   }   							/*所有頂點均已加入到S集合中*/
for (j=1;j<n;j++)     				/*打印結果*/
   { 
    cout<<"V(所求源點):(V0)到V"<<j<<"結點最短路徑長度="<<dist[j];
    p=pre[j];
    if(p!=0)cout<<"  其經過的結點有:";
    while (p!=0)
         { cout<<" V"<<p-1;
          p=pre[p-1];
           }
	cout<<endl;
    }
}
/*下面是為了測試dijkstra算法* 其圖的實例為例3.11(其中的結點下標都減1)*
 *其實驗結果見圖片*                                                   */
void InitGMatrix(int **&GA,int n)   //初始化圖的鄰接矩陣
{
	GA=new int *[n];
	int i,j;
	for(i=0;i<n;i++)GA[i]=new int[n];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)if(i==j)GA[i][j]=0;
	else GA[i][j]=max;
}
void main()
{
	int i,j,k,e,w,n;
	int **GA;
	cout<<"輸入待處理圖的頂點數：";
	cin>>n;
	InitGMatrix(GA,n);
	cout<<"輸入圖的總邊數:";
	cin>>e;
	for(k=1;k<=e;k++){
			cout<<"輸入第"<<k<<"條有向有權邊的起點和終點序號及權值:"<<endl;
			cin>>i>>j>>w;
			GA[i][j]=w;
		}
    dijkstra(0,GA,n);
}