//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :5  (5_5)                   *
//*PROGRAM          :最短路徑                   *
//*CONTENT          :迪杰斯特拉算法             *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 30000    //定義一個權值的最大值
#define MAX_VERTEX_NUM 20 //圖的最大頂點數
enum BOOL {False,True};
typedef struct
{int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣
 int vexnum,arcnum;                //圖的當前頂點和邊數
}Graph;
void CreateGraph(Graph &);    //生成圖的鄰接矩陣
void ShortestPath_DiJ(Graph,int,int[][MAX_VERTEX_NUM],int[]);
    //用迪杰斯特拉算法求從某一源點到其余頂點的最短路徑
void Print_ShortestPath(Graph,int,int[][MAX_VERTEX_NUM],int[]);
    //顯示最短路徑
void main()
{Graph G;  //采用鄰接矩陣結構的圖
 char j='y';
 int u;
 int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放從源點到各頂點的最短路徑
 int D[MAX_VERTEX_NUM];                 //存放從源點到各頂點的最短路徑的距離
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //------------------程序解說----------------------------
 printf("本程序將演示利用迪杰斯特拉算法求\n從圖的一點到其余頂點的最短路徑.\n");
 printf("首先輸入圖的頂點數和弧數.\n格式：頂點數，弧數；例如:5,7\n");
 printf("然后輸入各弧和權值.\n格式：弧尾，弧頭，權值；例如:\n1,2,10\n1,3,18\n2,4,5\n3,2,5\n4,3,2\n4,5,2\n5,3,2\n");
 printf("再輸入從哪個頂點出發，例如:1\n");
 printf("程序將會找出從1到其余頂點的最短路徑.\n");
 printf("10  1->2\n17  1->2->4->3\n15  1->2->4\n17  1->2->4->5\n");
 //------------------------------------------------------
 while(j!='N'&&j!='n')
      {CreateGraph(G);       //生成鄰接矩陣結構的圖
       printf("從哪個頂點出發:");
       scanf("%d",&u);  //輸入迪杰斯特拉算法中的起始頂點
       ShortestPath_DiJ(G,u,P,D); //利用迪杰斯特拉算法求最短路徑
       Print_ShortestPath(G,u,P,D); //顯示最短路徑
       printf("最短路徑演示完畢，繼續進行嗎?(Y/N)");
       scanf(" %c",&j);
     }
}

void CreateGraph(Graph &G)
{//構造鄰接矩陣結構的圖G
 int i,j;
 int start,end,weight;
 printf("請輸入圖的頂點數和弧數(頂點數，弧數):");
 scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數和邊數
 for(i=1;i<=G.vexnum;i++)
    for(j=1;j<=G.vexnum;j++)
      G.arcs[i][j]=INFINITY; //初始化鄰接矩陣
 printf("輸入各弧和權值，格式：弧尾，弧頭，權值\n");
 for(i=1;i<=G.arcnum;i++)
   {scanf("%d,%d,%d",&start,&end,&weight); //輸入邊的起點和終點及權值
    G.arcs[start][end]=weight;
   }
}
void ShortestPath_DiJ(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[])
{//用迪杰斯特拉算法求有向網G的v0頂點到其余頂點v的最短路徑P[v]及其帶權路徑長度D[v]
 //若P[v][0]≠0,表明從源點出發存在一條到頂點v的最短路徑，該路徑存放在P[v]中
 //final[v]為True則表明已經找到從v0到v的最短路徑
 int i,j,w,v;
 int min;
 BOOL final[MAX_VERTEX_NUM];
 for(v=1;v<=G.vexnum;v++)   //初始化
   {final[v]=False; D[v]=G.arcs[v0][v];
    for(i=0;i<=G.vexnum;i++) P[v][i]=0; //設空路徑
    //if(D[v]<INFINITY) P[v][0]=v0; //若從v0到v有直達路徑
   }
 D[v0]=0; final[v0]=True; //初始時，v0屬于S集
 //開始主循環，每次求得v0到某個頂點v的最短路徑，并加v到S集
 for(i=1;i<=G.vexnum;i++)  //尋找其余G.vexnum-1個頂點
   {v=0;
    min=INFINITY;
    for(w=1;w<=G.vexnum;w++)   //尋找當前離v0最近的頂點v
      if((!final[w])&&(D[w]<min))
	 {v=w;min=D[w];}
    if(!v) break;  //若v=0表明所有與v0有通路的頂點均已找到了最短路徑，退出主循環
    final[v]=True; //將v加入S集
    for(j=0;P[v][j]!=0;j++) ;
    P[v][j]=v;     //將路徑P[v]延伸到頂點v
    for(w=1;w<=G.vexnum;w++) //更新當前最短路徑及距離
      if(!final[w]&&(min+G.arcs[v][w]<D[w]))
	 {D[w]=min+G.arcs[v][w];
	  for(j=0;P[v][j]!=0;j++) P[w][j]=P[v][j];
	 }
   }
}

void Print_ShortestPath(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[])
{//顯示從頂點u到其余頂點的最短路徑及距離
 int v,j;
 printf("The shortest path from Vertex %d to the other Vertex:\n");
 for(v=1;v<=G.vexnum;v++)
      {if(P[v][0]==0) continue; //表明頂點v0到頂點v沒有通路
       printf("%-4d",D[v]);
       printf("%d->",v0);
       for(j=0;P[v][j]!=0;j++)
	 printf("%d->",P[v][j]);
       printf("\b\b  \n");
      }
}