/* file name: sh_path.c */
/*利用迪杰斯特拉算法去最短路徑*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX_V 100   /*最大節點數*/
#define VISITED 1
#define NOTVISITED 0
#define Infinite 1073741823

/* A[1..N][1..N] 為圖的鄰接矩陣 */
/* D[i] i=1..N 用來儲存某起始頂點到i節點的最短距離 */
/* S[1..N] 用來記錄頂點是否已經訪問過 */
/* P[1..N] 用來記錄最近經過的中間節點 */

long int A[MAX_V+1][MAX_V+1];
long int D[MAX_V+1];
long int S[MAX_V+1],P[MAX_V+1];
int source , sink , N;
int step = 1;

int top = -1;          /*堆棧指針*/
int Stack[MAX_V+1];   /*堆棧空間*/

void init();
int minD();
void output_step();
void output_path();
void Push(int);
int Pop();

void main()
{
	int t,I;

	init();
	output_step();

	for ( step =2;step <=N; step++ )
	{
		/* minD 傳回一值t使得D[t] 為最小 */
		t = minD();
		S[t] = VISITED;
		/* 找出經過t點會使路徑縮短的節點*/
		for ( I=1; I <= N; I++ )
		if ( (S[I] == NOTVISITED) && (D[t]+A[t][I] <= D[I]) )
		{
			D[I] = D[t] + A[t][I];
			P[I] = t;
		}
		output_step();
	}

	output_path();
}

void init()
{
	FILE *fptr;
	int i,j;
	long int weight;

	fptr = fopen("sh_path.dat","r");
	if ( fptr == NULL )
	{
		perror("sh_path.dat");
		exit(1);
	}

	fscanf(fptr,"%d",&N);       /*讀取圖節點數*/
	for ( i=1; i<=N; i++ )
		for ( j=1; j<=N; j++ )
			A[i][j] = Infinite; /*起始A[1..N][1..N]鄰接矩陣*/
 
	while ( fscanf(fptr,"%d %d %ld",&i,&j,&weight) != EOF )
	A[i][j] = weight;       /*讀取i節點到j節點的權weight */
	fclose(fptr);

	printf("Enter source node : ");
	scanf("%d",&source);
	printf("Enter sink node : ");
	scanf("%d",&sink);

	/* 起始各數組初值*/
	for ( i = 1; i <= N; i++ )
	{
		S[i] = NOTVISITED;  /*各頂點設為尚未訪問*/             
		D[i] = A[source][i]; /*記錄起始頂點至各頂點最短距離*/
		P[i] = source;       
	}
	S[source] = VISITED;   /*始起節點設為已經走訪*/
	D[source] = 0;
}

int minD()
{
	int i,t;
	long int minimum = Infinite;

	for ( i=1;i<=N;i++ )
		if ( (S[i] == NOTVISITED) && D[i] < minimum )
		{
			minimum = D[i];
			t = i;
		}

	return t;
}

/* 顯示目前的D數組與P數組狀況 */
void output_step()
{
	int i;

	printf("\n Step #%d",step);
	printf("\n================================================\n");
	for ( i=1; i<=N; i++ )
		printf("  D[%d]",i);
	printf("\n");
	for ( i=1; i<=N; i++ )
		if ( D[i] == Infinite )
			printf("  ----");
		else
			printf("%6ld",D[i]);
	printf("\n================================================\n");
	for ( i=1; i<=N; i++ )
		printf("  P[%d]",i);
	printf("\n");
	for ( i=1; i<=N;i++ )
		printf("%6ld",P[i]);
}

/*顯示最短路徑*/
void output_path()
{
	int node = sink;

	/*判斷是否起始頂點等于終點或無路徑至終點*/  
	if ( (sink == source) || (D[sink] == Infinite) )
	{
		printf("\nNode %d has no Path to Node %d",source,sink);
		return;
	}

	printf("\n");
	printf(" The shortest  Path from V%d to V%d :",source,sink);
	printf("\n------------------------------------------\n");

	/*由終點開始將上一次經過的中間節點推入堆棧至到起始節點*/ 
	printf("  V%d",source);
	while ( node != source )
	{
		Push(node);
		node  = P[node];
	}
	while( node != sink)
	{
		node = Pop();
		printf(" --%ld-->",A[ P[node] ][node]);
		printf("V%d",node);
	}

	printf("\n Total length : %ld\n",D[sink]);
}

void Push(int value)
{
	if ( top >= MAX_V )
	{
		printf("Stack overflow!\n");
		exit(1);
	}
	else
		Stack[++top] = value;
}

int Pop()
{
	if ( top < 0 )
	{
		printf("Stack empty!\n");
		exit(1);
	}

	return Stack[top--];
}