公园景点导游问题Dijkstra求最短路径

公园主要游览景点导游问题。问题描述：对某公园主要游览景点导游。功能需求：要求完成以下功能:.将公园内各景点输出。.将公园内每两个位置（若两个位置之间有直接路径）的距离输出。.修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；.求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径;.删除：删除任意一条边。.插入：插入任意一条边。代码#include<stdio.h>#include<iostream.h>#include<stdlib.h>#include<conio.h>#include<malloc.h>#include<string.h>#defineMAX1000-word资料-

#defineLENGTH6#definevalueinttypedefstruct(charname[30];intnum;}VEXTYPE;typedefstruct(VEXTYPEvexs[LENGTH];valuearcs[LENGTH][LENGTH];intvexnum,arcnum;}MGraph;MGraphb;MGraphInitGraph()(inti,j;MGraphG;〃初始景点数为6,〃初始景点数为6,即图的顶点//初始景点最大路径数G.arcnum=15;数为15，即图的最大边数-word-word资料-for(i=0;i<G.vexnum;i++)G.vexs[i].num=i;strcpy(G.vexs[0].name,"景点A");〃景点Astrcpy(G.vexs[1].name,"景点B");〃景点Bstrcpy(G.vexs[2].name,"景点C");〃景点Cstrcpy(G.vexs[3].name,"景点D");〃景点Dstrcpy(G.vexs[4].name,"景点E");〃景点Estrcpy(G.vexs[5].name,"景点F");〃景点Ffor(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j]=MAX;G.arcs[0][1]=50;//景点A与景点B的距离为50G.arcs[0][2]=20;//景点A与景点C的距离为20G.arcs[0][3]=30;//景点A与景点D的距离为30G.arcs[1][2]=10;//景点B与景点C的距离为10G.arcs[1][4]=70;//景点B与景点E的距离为70G.arcs[2][5]=90;//景点C与景点F的距离为90G.arcs[3][5]=40;//景点D与景点F的距离为40G.arcs[4][5]=50;//景点E与景点F的距离为50for(i=0;i<G.vexnum;i++)-word资料-

for(j=0;j<G.vexnum;j++)G.arcs[j][i]=G.arcs[i][j];returnG;)voidMenu() 〃功能需求选项菜单cout<<-*********功能需求选项菜单*********5";cout<<"1一输出公cout<<"1一输出公内景点5”;cout<<- 2一输出每两个直接相连景点的距离\n";cout<<" 3一修改两个景点距离\n”;cout<<- 4一两景点之间最短路径\n”;cout<<- 5一删除某条边（两个直接相连景点的连线）\n";cout<<" 6---插入某条边\n”;cout<<"0一退出5”;cout<<"0一退出5”;cout<<-*******某公主要游览景点导游m\n”;)//功能//功能1输出公园内景点cout<<"公园内各景点”<<endl;for(inti=0;i<G->vexnum;i++)-word资料-cout<<G->vexs[i].name<<""<<endl;)//功能//功能2输出公园内每两个直接相连景点的距离for(inti=0;i<G->vexnum;i++)for(intj=0;j<G->vexnum;j++)if(G->arcs[i][j]<MAX){cout<<G->vexs[i].name<<" >"<<G->vexs[j].name<<”的距离为"<<G->arcs[i][j]<<endl;))voidChange(MGraph*G) //功能3修改：修改两个景点距离（权值）{intv0,v1,length;cout<<“修改：输入两顶点\n";cin>>v0;cin>>v1;cout<<"输入距离:“；cin>>length;G->arcs[v0][v1]=G->arcs[v1][v0]=length;-word资料-voidDijkstra(MGraph*G) //功能4.求最短路径输出给定两景点之间的最短路径的长度及途经的各景点( 〃使用Dijkstra算法求解最短路径intv,w,i,min,t=0,x,v0,v1;intfinal[20],D[20],p[20][20];cout<<”请输入起始顶点八n”;cin>>v0;if(v0<0||v0>G->vexnum)(cout<<“此点不存在!请重新输入顶点:“；cin>>v0;)cout<<”请输入结束顶点:\n”;cin>>v1;if(v1<0||v1>G->vexnum)(cout<<“此点不存在!请重新输入顶点:";cin>>v1;-word资料-)for(v=0;v<G->vexnum;v++)(final[v]=0;D[v]=G->arcs[v0][v];for(w=0;w<G->vexnum;w++)P[v][w]=0;if(D[v]<MAX)(P[v][v0]=1;p[v][v]=1;))D[v0]=0;final[v0]=1;for(i=1;i<G->vexnum;i++)(min=MAX;for(w=0;w<G->vexnum;w++)if(!final[w])if(D[w]<min){v=w;min=D[w];}final[v]=1;for(w=0;w<G->vexnum;w++)if(!final[w]&&(min+G->arcs[v][w]<D[w]))-word资料-D[w]=min+G->arcs[v][w];for(x=0;x<G->vexnum;x++)p[w][x]=p[v][x];p[w][w]=1;))cout<<"从"<<G->vexs[v0].name<<"到"<<G->vexs[v1].name<<"的最短路径长度为："<<D[v1]<<endl;cout<<“途经的景点：“<<endl;for(intj=0;j<G->vexnum;j++)(if(p[v1][j]==1)cout<<G->vexs[j].name<<endl;))voidDeleteArc(MGraph*G) 〃功能5删除:删除任意一条边。(- . -word资料-intv0,v1;cout<<”请输入两顶点八n”;cin>>v0>>v1;G->arcs[v0][v1]=MAX;G->arcs[v1][v0]=MAX;)voidInsertArc(MGraph*G) //功能6插入：插入任意一条边。(intv0,v1,l=0;cout<<”请输入两顶点八n”;cin>>v0>>v1;cout<<”请输入路径长度:5”；cin>>l;G->arcs[v0][v1]=l;G->arcs[v1][v0]=l;)voidmain(){inta;b=InitGraph();Menu();-word资料-cin>>a;while(a!=0)(switch(a)(case1:PutOutVex(&b);Menu();break;case2:PutOutArc(&b);Menu();break;case3:Change(&b);Menu();break;case4:Dijkstra(&b);Menu();break;case5:DeleteArc(&b);Menu();break;case6:InsertArc(&b);Menu();break;case0:exit(1);break;default:break;)cin>>a;附录；截菜单显示-word资料-功能1输出公园内景点功能2输出每两个直接相连景点的距离某公元主要游资景只寻淤i***-U0_u@O0_u@O某公元主要游资景只寻淤i***-U0_u@O0_u@O0-u-H-00-u-H-523517219347594s点点占谕点点占低点点占咎,点点占雷F®年r旦管5置置置F旦置置置京豆量>®-量>口同m'--之^*^>>>>>>>>>>>>>>>?.m匕匕攵----------------力壮廿E一H理福*__一---------------M---nA-A-R-DB-Jc-cD-』F-EF-F-F-mL2-*上彼小点点点点点点点点点点点点点点八三K昌置置置昌置置置虽置置岂量置宁KMMJ-MJ-MJ-MJ--.-7

2J...-'...-U-...IIJ2JJ2JJ2JJ2J...-.'...-^...-^J2J.;J2JJ.ll<Hte-rm」勖

离高离离离鬲禺离离离昌离离高岛离？割雷

二二一「二一「二R三二二「二一「二一「三二一一□一一「二一「三二一一「二一「二一「一一耳片由F

offnffisnffnff££nffnff££HEnfffi£HEJmmJrnTur^

,|7^.勺.—可勺勺.勺—Tr-UTTV勺勺.JT-C:--勺.先TE..F1J,

nftHnR"nnnnpfrHA"nnnftHfrMnfl«nnn„rtnAtf.RMnnn&H_Nr\3-3

dcdaceadfafbfgdE、_t<F2与

园F-I■■功能4两景点BF之间最短路径-word资料-功能3修改两个景点DF距离，并显示修改结果（截图中景点D景点F距离为60）・।'D:\Vi5ualC-I--6.0Sects\zdu\Debug\zdu.eie"出出暨E除/..占任爷吊点点点点点点点点占D|昌昌共置篁曾曼昌目量不景XIJ2J..口.勺.♦JJ.-z^l-JJZ2J离离离离离离离、昌离离离r一「三n出出暨E除/..占任爷吊点点点点点点点点占D|昌昌共置篁曾曼昌目量不景XIJ2J..口.勺.♦JJ.-z^l-JJZ2J离离离离离离离、昌离离离r一「三n一一n一一「二二三二一一n-□一二二一n=r二BCDACEHBFAPB与£害¥与营^心点匕营学号-景景景景景景景导景景导鲁>>>>>>>>>>>>A--u0-uQ00_uo0甘S*5235172193-R7回两个zlsl-品品总品品品品是总品品品_C7■:.-c-:.J7-T-I7-VH^irnM—.:-CT:UJT-T-ij二"J""TTUJ"*FTnJ*TT/r*rluf*nITT—PF"“r*rT^I喑相w弟—背点幅距通两姓国；.目占甘药L三内工L面边+口口葭公每两弄某早功能5删除BC边并显示结果（截中无景点B--＞景点C的直接距离）-word资料-

*豆解公每向点某某0RAnBBCil..---LI..-2J..--2J