12-3.c

单源点最短路径贪心算法：用到Dijkstra算法

#include "stdio.h"
#include <malloc.h>
typedef int DataType;
ShortestPath(int s, DataType d[], int p[])
{// 寻找从顶点s出发的最短路径, 在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;
			}
		}
	}
}