zuiduanlujing.cpp

数据结构最短路径的实现方法 从始点v0开始

#include<stdlib.h>
#include<stdio.h>
#define mvnum 100 //最大顶点数
#define maxint 32767 //最大整数
enum boolean {FALSE,TRUE};
typedef struct {
	int vexs[mvnum];  //顶点数组,假设为int类型
	int arcs[mvnum][mvnum];  //邻接矩阵,假设为int类型
} MGraph;
int D1[mvnum],P1[mvnum];
int D[mvnum][mvnum],P[mvnum][mvnum];

void CreateMGraph(MGraph *G,int n,int e){//采用邻接矩阵表示图
	int i,j,k,w;
	for (i=1;i<=n;i++)
		G->vexs[i]=i;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			G->arcs[i][j]=maxint;   //初始化邻接矩阵
	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顶点到其他顶点v的最短路经P[v]及权D[v]
  //S[v]为真当且仅当v属于S,即已求得从v1到v的最短路经
	int D2[mvnum],P2[mvnum];
	int v,i,w,min;
	enum boolean S[mvnum];
	for (v=1;v<=n;v++){//初始化S,D
		S[v]=FALSE;
		D2[v]=G->arcs[v1][v];
		if (D2[v]<maxint)
			P2[v]=v1;   //v1是v的前趋
		else
			P2[v]=0;    //v无前趋
	}//end_for
	D2[v1]=0;S[v1]=TRUE;   //S集初始时只有源点,源点到源点的距离为0
    //开始循环,每次求得v1到某个顶点的最短路经,并加v到S集中
	for (i=2;i<=n;i++){ //其余n-1个顶点
		min=maxint;
		for (w=1;w<=n;w++)
			if (!S[w] && D2[w]<min)
			{v=w;min=D2[w];}  //w顶点离v1更近
			S[v]=TRUE;
			for (w=1;w<=n;w++) //更新当前最短路经及距离
				if (!S[w] && (D2[v]+G->arcs[v][w]<D2[w])) {//修改D2[w]及P2[w],w属于V-S
					D2[w]=D2[v]+G->arcs[v][w];
					P2[w]=v;
				}//end_if
	}//end_for
	printf("路经长度     路经\n");
	for(i=1;i<=n;i++){
		printf("%5d",D2[i]);
		printf("%5d",i);v=P2[i];
		while (v!=0){
			printf("<-%d",v);
			v=P2[v];
		}
		printf("\n");
	}
}

void main()
{ MGraph *G;
  int n,e,v;
  G=(MGraph *)malloc(sizeof(MGraph));
  printf("输入图中顶点个数和边数n,e:");
  scanf("%d,%d",&n,&e);
  CreateMGraph(G,n,e);   //建立图的存储结构
  printf("求单源路经,输入源点v: ");
  scanf("%d",&v);
  Dijkstra(G,v,n);  //调用迪杰斯特拉算法
  printf("结束!\n");
}