dijkstra.cpp

用Dijkstra算法求解最短路径

#include<stdio.h>
#include<malloc.h>
#define MVNum 100    //最大顶点数
#define Infinity 32767
typedef struct{
	char vexs[MVNum];
	int arcs[MVNum][MVNum];
}MGraph;

void CreateMGraph(MGraph *G,int v,int e){
	int i,j,k,w;
	for(i=1;i<=v;i++)
		G->vexs[i]=(char)i;
	for(i=1;i<=v;i++)
		for(j=1;j<=v;j++)
			G->arcs[i][j]=Infinity;
	printf("输入%d条边的i,j及w:\n",e);
	for(k=1;k<=e;k++)
	{
		scanf("%d,%d,%d",&i,&j,&w);
		G->arcs[i][j]=w;
	}
	printf("有向图的存储结构建立完毕！\n");
}


void Dijkstra(MGraph *G,int v1,int n)
{      //用Dijkstra算法求v1到其他结点的最短路径
	int D[MVNum];      //权值
	int P[MVNum];      //最短路径
	int F[MVNum];      //F[v]为真当且仅当已经求得v1到v的最短路径
	int v,i,w,min,flag=0;
	for(v=1;v<=n;v++)
	{        //初始化D,P,F
		F[v]=0;
		D[v]=G->arcs[v1][v];
		if(D[v]<Infinity)
			P[v]=v1;   //v1是v的前驱
		else
			P[v]=0;  //v无前驱
	}
	D[v1]=0;
	F[v1]=1;
	for(i=2;i<=n;i++)
	{      //循环求得v1到某个结点v的最短路径
		min=Infinity;
		for(w=1;w<=n;w++)
			if(!F[w]&&D[w]<min)
				{
					v=w;
					min=D[w];
					flag=1;
				}
		if(flag==0)
		    v=v1;
		F[v]=1;
		for(w=1;w<=n;w++)   //更新当前最短路径及距离
			if(!F[w]&&(min+G->arcs[v][w]<D[w]))
			{
				D[w]=min+G->arcs[v][w];
				P[w]=v;
			}
	}
	printf("路径长度    路径\n");
	for(i=1;i<=n;i++)
	{
		if(flag==0)
		{
		    printf("%5d",D[i]);
		    printf("     v%d",v1);
			printf("\n");
		}
		else
		{
	    	printf("%5d",D[i]);
		    printf("     v%d",i);
		    v=P[i];
		    while(flag&&v!=0){
			    printf("<-v%d",v);
			    v=P[v];
			}
			if(flag==0)
			{
				printf("%5d",D[i]);
				printf("     v%d",v1);
			}
			printf("\n");
		}
	}
}


void main(){
	int v,n,e;
	MGraph *G;
	G=(MGraph *)malloc(sizeof(MGraph));
	printf("输入图中顶点个数和边数n,e:  ");
	scanf("%d,%d",&n,&e);
	CreateMGraph(G,n,e);
	printf("\n输入源点v: ");  
	scanf("%d",&v);
	printf("从源点v%d到其他结点的最短距离及路径为：\n",v);
	while(v>=1&&v<=n)
	{
	    Dijkstra(G,v,n);
		printf("\n输入源点v: ");  
	    scanf("%d",&v);
		printf("从源点v%d到其他结点的最短距离及路径为：\n",v);
	}
}