4-2.c

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

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

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

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

AdjLGraph g;
int main()
{
	void PrintPath(int path[MaxVertices], int v);
	
	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;
	int v0;
	
	printf("input the first plot: ");
	scanf("%d", &v0);
	memset(distance, 0, sizeof(distance));
	memset(path, 0, sizeof(path));
	
	CreatGraph(&g, a, n, row, e);
	for(i=0;i<n;i++)
	{
		printf("%d %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, v0, distance, path);
	
	printf("\n从节点 %d 到其他各点的最短距离为:\n",g.a[v0].data);
	for(i=0;i<n;i++)
	printf("到节点 %d 的最短距离为%d:\n", g.a[i].data, distance[i]);
	
	printf("\n从节点 %d 到其他各点的最短路径的前一节点为:\n", g.a[v0].data);
	for(i=0;i<n;i++)
	{
		if(path[i]!=-1)
		{
			printf("到节点 %d 的路径为: %d",g.a[i].data, g.a[v0].data);
			PrintPath(path,i);
			printf("\n");
		}
	}
	
	getchar();
	getchar();
}


void PrintPath(int path[MaxVertices],int v)
{
	if(path[v]==-1)return ;
	else PrintPath(path, path[v]);
	printf("->%d",g.a[v].data);
}