算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計《蘭州道路交通網(wǎng)絡(luò)信息查詢源程序》

蘭州道路交通網(wǎng)絡(luò)信息查詢#include<stdio.h>#include<stdlib.h>#defineMVNum100//最大頂點數(shù)#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//頂點數(shù)組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;voidCreateMGraph(MGraph*G,intn,inte){//采用鄰接矩陣表示法構(gòu)造有向圖G，n，e表示圖的當(dāng)前頂點數(shù)和邊數(shù)intarcs[MVNum][MVNum];inti,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint;//初始化鄰接矩陣printf("shuru%dtiaobiandei,j,w:\n",e);for(k=1;k<=e;k++){//讀入e條邊，建立鄰接矩陣scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf("youxiangtudecunchujiegoujianliwanbi!\n");}voidDijkstra(MGraph*G,intv1,intn){//用Dijkstra算法求有向圖G的v1頂點到其他頂點v的最短路徑P[v]及其權(quán)D[v]//設(shè)G是有向圖的鄰接矩陣，若邊〈i，j〉不存在，則G[i][j]=Maxint//S[v]為真當(dāng)且僅當(dāng)v∈S，即已求得從v1到v的最短路徑intD2[MVNum],P2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){//初始化S和DS[v]=FALSE;//置空最短路徑終點集D2[v]=G->arcs[v1][v];//置初始的最短路徑值if(D2[v]<Maxint)P2[v]=v1;//v1是v的前趨（雙親）elseP2[v]=0;//v無前趨}D2[v1]=0;S[v1]=TRUE;//S集初始時只有源點，源點到源點的距離為0//開始循環(huán)，每次求得v1到某個v頂點的最短路徑，并加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++)//更新當(dāng)前最短路徑及距離if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];P2[w]=v;}//End_if}//End_forprintf("lujingchangdulujing\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");}}voidFloyd(MGraph*G,intn){intD[MVNum][MVNum],P[MVNum][MVNum];inti,j,k,v,w;for(i=1;i<=n;i++)//設(shè)置路徑長度D和路徑path初值for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)P[i][j]=j;//j是i的后繼else P[i][j]=0; D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++) {for(i=1;i<=n;i++)//做k次迭代，每次均試圖將頂點k擴充到當(dāng)前求得的從i到j(luò)的最短路徑Pij上 for(j=1;j<=n;j++) {if(D[i][k]+D[k][j]<D[i][j]){ D[i][j]=D[i][k]+D[k][j];//修改長度 P[i][j]=P[i][k]; }}}}intD1[MVNum],P1[MVNum];intD[MVNum][MVNum],P[MVNum][MVNum];voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf("shurutuzhongdingdiangeshuhebianshun,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);//建立圖的存儲結(jié)構(gòu)while(xz!=0){printf("*****qiudefangzhijiandezuiduanlujing*****\n");printf("==============================\n");printf("1,qiuyigedefangdaosuoyoudefangdezuiduanlujing\n");printf("2,qiurenyilianggedefangzhijiandezuiduanlujing\n");printf("===============================\n");printf("qingxuanze:1or2,xuanze0exit:");scanf("%d",&xz);if(xz==2){Floyd(G,n);//調(diào)用費洛伊德算法printf("shuruqidianhezhongdian:v,w:");scanf("%d,%d",&v,&w);k=P[v][w];if(k==0)printf("dingdian%ddao%dwulujing!\n",v,w);else{printf("congdingdian%ddao%ddezuiduanlujingshi:%d",v,w,v);while(k!=w){printf("->%d",k);//輸出后繼頂點k=P[k][w];//繼續(xù)找下一個后繼頂點}printf("->%d",w);//輸出終點wprintf("lujingchangdu:%d\n",D[v][w]);}}elseif(xz==1){