求最短路径Dijkstra算法

【问题描述】 试设计一个算法，求图中一个源点到其他各顶点的最短路径。 【基本要求】 （1）用邻接表表示图； （2）按长度非递减次序打印输出最短路径的长度及相应路径。

#include
#include
#include
#include
typedef char DataType;
#define MaxVertices 10
#include “AdjLGraph.h“
void main（）
{
	int inelenenkjttf;int s[MaxVertices]t[MaxVertices];
	int RowColWei;
	int distance[MaxVertices];
	int path[MaxVertices][MaxVertices];
	AdjLGraph g;
	struct Node *p*q;
	char v[MaxVertices];

	AdjInitiate（&g）;

	printf（“输入结点序列：“）;
	scanf（“%s“v）;
	len=strlen（v）;
	for（i=0;i		InsertVertex（&giv[i]）;

	printf（“输入边数：“）;
	scanf（“%d“&n）;
	printf（“是否为有向图？是则输入1，否则输入2：“）;
	scanf（“%d“&en）;
	e=en*n;
	printf（“输入边的两结点和权值：\n“）;
	for（i=0;i	{
		scanf（“%d%d%d“&Row&Col&Wei）;
		InsertEdge（&gRowColWei）;
	}
	printf（“序号与结点：\n“）;
	for（i=0;i		printf（“（%d）:%c\t“g.a[i].sorceg.a[i].data）;
	printf（“\n选择源点的序号：“）;
	scanf（“%d“&k）;

	for（i=0;i	{
		distance[i]=0;
	}
	for（i=0;i	{	for（j=0;j			path[i][j]=-1;
	}
	for（i=0;i	{
		s[i]=0;
		t[i]=0;
	}

	q=g.a[k].adj;
	while（q!=NULL）
		{
		distance[q->dest]=q->weight;
		path[q->dest][0]=k;
		path[q->dest][1]=q->dest;
		q=q->next;
		}
	s[k]=1;
	while（!condition（slen））
	{
		tt=MinDis（distanceslen）;
		j=0;
		p=g.a[tt].adj;
		while（p!=NULL&&distance[tt]!=0）
		{
			if（distance[p->dest]>distance[tt]+p->weight||distance[p->dest]==0）
			{
				distance[p->dest]=distance[tt]+p->weight;
				j=0;
				while（path[tt][j]!=-1）
				{
					path[p->dest][j]=path[tt][j];
					j++;
				}
				
				path[p->dest][j]=p->dest;
				for（i=j+1;i					path[p->dest][i]=-1;
			}
			p=p->next;
		}
		s[tt]=1;
	}
	t[k]=1;
	while（!condition（tlen））
	{
		j=0;
		f=MinDis（distancetlen）;
		t[f]=1;
		printf（“\n最短距离\t%d“distance[f]）;
		printf（“\t“）;
		while（path[f][j]!=-1）
		{
			printf（“%c-->“g.a[path[f][j]].data）;
			j++;
		}
		printf（“\b\b\b    “）;
	}
	printf（“\n“）;





} 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        1598  2009-04-24 04:30  AdjLGraph.h
     文件        2037  2009-05-09 14:28  Dijkstra1.c