ldijkstratest1.c

《数据结构-使用C语言》第三版

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>

//typedef char DataType;
typedef int DataType;
#define MaxSize 100
#define MaxVertices 10
#define MaxWeight 10000

#include"AdjLGraph.h"
#include"LDijkstra.h"

int main()
{
	AdjLGraph g;
	//char a[]={'A','B','C','D','E','F','G','H'};
	//RowColWeight row[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50},
						//{0,5,30},{1,6,35},{4,7,23},{1,0,40}};
	
	int a[]={1,2,3,4,5,6,};
	RowColWeight row[]={{0,1,20},{0,2,4},{0,3,34},{1,0,20},{1,3,34},
						{1,5,25},{2,0,4},{2,4,14},{3,0,34},{3,1,8},
						{3,4,12},{3,5,10},{4,2,14},{4,3,12},{4,5,30},
						{5,1,25},{5,3,10},{5,4,30}};
	int i, n=6, e=18;
	int distance[MaxVertices],path[MaxVertices];
	Edge *p;

	memset(distance, 0, sizeof(distance));
	memset(path, 0, sizeof(path));
	
	CreatGraph(&g, a, n, row, e);
	for(i=0;i<n;i++)
	{
		printf("%c %d\n",g.a[i].data, g.a[i].sorce);
		p=g.a[i].adj;
		while(p!=NULL)
		{
			printf("\t%d %d\n",p->dest, p->dis);
			p=p->next;
		}
	}

	DijkstraL(g, 0, distance, path);
	
	printf("\n从节点 %c 到其他各点的最短距离为:\n",g.a[0].data);
	for(i=0;i<n;i++)
	printf("到节点 %c 的最短距离为%d:\n", g.a[i].data, distance[i]);
	printf("\n从节点 %c 到其他各点的最短路径的前一节点为:\n", g.a[0].data);
	for(i=0;i<n;i++)
	if(path[i]!=-1)
	printf("到节点 %c 的前一节点为%c:\n",g.a[i].data, g.a[path[i]].data);
	
	getchar();
}