shortestpath.cpp

全国交通图最短路径~大二数据结构课程设计题目~亲测~完美版

#define INFINITY 10000
#define MAX_VERTEX_NUM 32
#define MAX_ARC_NUM 50
#include<stdio.h>
#include<string.h>

typedef struct{
	//int v;
    char city[20]; 
}VertexType;//顶点

typedef struct {
    VertexType vex[MAX_VERTEX_NUM];
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int vexnum,arcnum;//图的顶点数和弧数 
}MGraph;//图

typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef int PathMatrix[MAX_VERTEX_NUM];


void CreateDG(MGraph &G){
		int i,j;
		char string[][20]={"Beijing","Haerbin","Changchun","Shenyang","Tianjin","Dalian","HHHT","Yinchuan",
		               "WLMQ","Xining","Lanzhou","Xi'an","Taiyuan","Zhengzhou","Xuzhou","Shanghai",
		               "Nanjing","Hefei","Wuchang","Changsha","Chongqinh","Chengdu","Kunming","Guiyang",
					   "Zhuzhou","Nanchang","Hangzhou","Fuzhou","Shenzhen","Guangzhou","Liuzhou","Nanning"
					  };
		G.vexnum=MAX_VERTEX_NUM;
		G.arcnum=MAX_ARC_NUM;

		for(i=0;i<G.vexnum;++i)
			for(j=0;j<G.vexnum;++j)
				G.arcs[i][j]=INFINITY;

       for(i=0;i<MAX_VERTEX_NUM;i++)strcpy(G.vex[i].city,string[i]);
	   
    FILE *fp;
	char filename[10];
	int ch;
    fp=fopen("graph.dat","r");
	ch=fgetc(fp)-48;
	while(!feof(fp)){
		int i=0,j=0;
		
		if(ch!=0)i=10*ch;
	    ch=fgetc(fp)-48;
		i=i+ch;

		ch=fgetc(fp)-48;
		if(ch!=0)j=10*ch;
	    ch=fgetc(fp)-48;
		j=j+ch;

        G.arcs[i][j]=0;
		ch=fgetc(fp)-48;
		if(ch!=0)G.arcs[i][j]=1000*ch;
		ch=fgetc(fp)-48;
		G.arcs[i][j]+=100*ch;
		ch=fgetc(fp)-48;
		G.arcs[i][j]+=10*ch;
		ch=fgetc(fp)-48;
		G.arcs[i][j]+=ch;
		ch=fgetc(fp)-48;
	}//while

	  
}

    

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){
	int v,w,i,min;
	bool final[MAX_VERTEX_NUM];	

	for(w=0;w<MAX_VERTEX_NUM;w++)P[w]=-1;
	for(v=0;v<G.vexnum;++v){
		final[v]=false;
		D[v]=G.arcs[v0][v];
        if(D[v]<INFINITY)P[v]=v0;	
	}//for

	D[v0]=0;
	final[v0]=true;//初始化，v0顶点属于S集
//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集
	for(i=1;i<G.vexnum;++i){//其余G.vexnum－1个顶点
		min=INFINITY;//当前所知离v0顶点最近距离
		for(w=0;w<G.vexnum;++w)
			if(!final[w])//w顶点在V－S中
				if(D[w]<min){//w顶点离v0更近
					v=w;
					min=D[w];
				}

         final[v]=true;//离v0顶点最近的v加入S集

		 for(w=0;w<G.vexnum;++w)//更新当前最短路径及距离	 
			 if(!final[w]&&(min+G.arcs[v][w]<D[w])){//修改D[w]和P[w],w∈V-S
				 D[w]=min+G.arcs[v][w];
				 P[w]=v;
				 
			 }//if
	}//for
}//ShortestPath_DIJ

void Output_ShortestPath(MGraph G,int v0,int vn,PathMatrix P,ShortPathTable D){
	printf("从(%d)%s到(%d)%s的最短距离为%d公里。\n\t",v0,G.vex[v0].city,vn,G.vex[vn].city,D[vn]);
	printf("其路径为:");
	
	int t;
	int i;
	int a[MAX_VERTEX_NUM];//将路径输入a[]
	printf("%s-->",G.vex[v0].city);
	for(i=0;i<MAX_VERTEX_NUM;i++)a[i]=-1;
	
	for(t=P[vn],i=MAX_VERTEX_NUM-1;(t!=-1)&&(t!=v0);i--){
        a[i]=t;
		t=P[t];
	}

	for(i=0;i<MAX_VERTEX_NUM;i++){
		if(a[i]==-1)i++;
		else printf("%s-->",G.vex[a[i]].city);
	}
		printf("%s",G.vex[vn].city);
}



void main()
{
	int v0,vn,ch=1;
	ShortPathTable D;
	PathMatrix P;
	MGraph G;
	printf("  \t\t\t已导入地图graph相关城市");
	printf("\n ****************************************************************************\n");
	printf("\t0北京Beijing\t1哈尔滨Haerbin\t2长春Changchun\t3沈阳Shenyang\n\t4天津Tianjin\t5大连Dalian\t6呼和浩特HHHT\t7银川Yinchuan\n\t8乌鲁木齐WLMQ\t9西宁Xining\t10兰州Lanzhou\t11西安Xian\n\t12太原Taiyuan\t13郑州Zhengzhou\t14徐州Xuzhou\t15上海Shanghai\n\t16南京Nanjing\t17合肥Hefei\t18武昌Wuchang\t19长沙Changsha\n\t20重庆Chongqinh\t21成都Chengdu\t22昆明Kunming\t23贵阳Guiyang\n\t24株洲Zhuzhou\t25南昌Nanchang\t26杭州Hangzhou\t27福州Fuzhou\n\t28深圳Shenzhen\t29广州Guangzhou\t30柳州Liuzhou\t31南宁Nanning\n ");
   	printf("****************************************************************************\n");
	printf("\n");
   
    CreateDG(G);
	
	while(ch){	
		printf("输入起点城市编号");  
		scanf("%d",&v0);
		printf("输入终点城市编号");   
		scanf("%d",&vn);	
		ShortestPath_DIJ(G,v0,P,D);
		printf("\n****************************************************************************\n");
		Output_ShortestPath(G,v0,vn,P,D);
		printf("\n*****************************************************************************\n");

		printf("\n\n");   
		printf("继续查询请按1\t退出请按0");	
		printf("\n");	
		scanf("%d",&ch);
	
	}

	
}