实验十五、基于Dijsktra算法的最短路径

1 实验目的

掌握求解最短路径的Dijsktra算法。

2 实验内容

  1. 建立如图所示的邻接矩阵；

    2）根据Dijsktra算法求其从指定源点的最短路径。

算法复杂度：O(N^2)
补充：dijkstra可以利用堆的数据结构完成优化达到nlogn的时间复杂度

Code：

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

#define MAX_SIZE 20
#define OK 1
#define NO 0
#define INF 0x3f3f3f3f

typedef int Status;
typedef int ElemType;
typedef char InfoType;

typedef struct
{
	InfoType *info;
	ElemType Vertex;
}ArcCell,*ImageTable;

typedef struct
{
	ImageTable *Matrix; //临接矩阵
	ArcCell vexs[MAX_SIZE]; //顶点表
	int vexnum,arcnum; //统计顶点和边(弧)的个数
	Status Tag; //图的种类 1,2,3,4分别对应无向图、无向网、有向图、有向网
}MGraph;

Status InitMatrix(MGraph *Node)
{
	int i;
	Node->Matrix=(ImageTable *)malloc(Node->vexnum*sizeof(ImageTable));
	for(i=0;i<Node->vexnum;i++)
	{
		Node->Matrix[i]=(ImageTable)malloc(Node->vexnum*sizeof(ArcCell));
		if(Node->Matrix[i]==NULL)
			return NO;
	}
	return OK;
}

Status CreatGraph(MGraph *Node)
{
	int i,j,w;
	int v1,v2;

	for(i=0;i<Node->vexnum;i++)
	{
		for(j=0;j<Node->vexnum;j++)
			Node->Matrix[i][j].Vertex=INF;
	}

	printf("输入%d条弧的i,j及w:\n",Node->arcnum);
	for(i=0;i<Node->arcnum;i++)
	{
		getchar();
		scanf("%d,%d,%d",&v1,&v2,&w);
		Node->Matrix[v1-1][v2-1].Vertex=w;
	}

	printf("\n该临接矩阵是:\n");
	for(i=0;i<Node->vexnum;i++)
	{
		for(j=0;j<Node->vexnum;j++)
			if(Node->Matrix[i][j].Vertex==INF)
				printf("∞%c"," \n"[j+1==Node->vexnum]);
			else
				printf("%2d%c",Node->Matrix[i][j].Vertex," \n"[j+1==Node->vexnum]);
	}

	return OK;
}

void dijkstra(MGraph *Node,int start)
{
	int i,v,u;
	int *vis=(int *)malloc(Node->vexnum*sizeof(int));
	int *mincost=(int *)malloc(Node->vexnum*sizeof(int));
	int *previs=(int *)malloc(Node->vexnum*sizeof(int));

	for(i=0;i<Node->vexnum;i++)
	{
		vis[i]=0;
		mincost[i]=Node->Matrix[start-1][i].Vertex;
		previs[i]=start-1;
	}

	vis[start-1]=1;
	mincost[start-1]=0;
	
	for(i=2;i<=Node->vexnum;i++)
	{
		v=-1;
		for(u=0;u<Node->vexnum;u++)
			if(!vis[u] && (v == -1 || mincost[u]<mincost[v]))
				v=u;

		vis[v]=1;

		for(u=0;u<Node->vexnum;u++)
			if(mincost[u]>mincost[v]+Node->Matrix[v][u].Vertex)
			{
				mincost[u]=mincost[v]+Node->Matrix[v][u].Vertex;
				previs[u]=v;
			}
	}
	
	printf("路径长度 路径\n");
	for(i=0;i<Node->vexnum;i++)
	{
		if(mincost[i]!=INF)
			printf("%5d ",mincost[i]);
		else
			printf("%5s ","∞");
		for(u=i;;u=previs[u])
		{
			printf("%d",u+1);
			if(u==start-1)
				break;
			printf("<-");
		}
		printf("\n");
	}
	
	free(vis);
	free(mincost);
	free(previs);
}

int main()
{
	MGraph image;
	int v;
	printf("输入图中顶点个和弧数:");
	scanf("%d,%d",&image.vexnum,&image.arcnum);
	image.Tag=4;
	InitMatrix(&image);
	CreatGraph(&image);
	while(1)
	{
		printf("\n求单源路径,输入源点v:");
		scanf("%d",&v);
		if(v==-1)
			break;
		dijkstra(&image,v);
	}
	return 0;
}

/* Matrix input: 1,3,13 1,7,17 7,6,76 7,4,74 3,2,32 6,1,61 6,4,64 4,5,45 5,6,56 2,6,26 */