#include "stdio.h"
#include <malloc.h>
typedef int DataType;
ShortestPath(int s, DataType d[], int p[])
{// 尋找從頂點s出發(fā)的最短路徑, 在d中返回最短距離
// 在p中返回前繼頂點
	int i,j,*v,*w;
	Chain L; // 路徑可到達頂點的列表
	ChainIterator I;
	if (s<1||s>n) 
	{
		printf("超出邊界。");
		eixt(1);
	}
	// 初始化d, p, L
	for (i = 1; i <= n; i++){
		d[i] = a[s][i];
	if (d[i]==0) 
		p[i] = 0;
	else {
		p[i] = s;
		Insert(&L 0 , i ) ; 
	}
	// 更新d, p
	while (!IsEmpty(L)) {// 尋找具有最小d的頂點v
		*v = Initialize(&I,L);
		*w = I.Next(&I);
		while (w) {
			if (d[*w] < d[*v]) v = w;
				w = Next(&I);
		}
	// 從L中刪除通向頂點v的下一最短路徑并更新d
		i = *v;
		Delete(&L,* v ) ;
		for (j = 1; j <= n; j++) {
			if (a[i][j] != 0 && (!p[j] ||d[j] > d[i] + a[i][j])) 
			{
				// 減小d [ j ]
				d[j] = d[i] + a[i][j];
				// 將j加入L
				if (!p[j]) Insert(&L0,j);
					p[j] = i;
			}
		}
	}
}