《公园景点导游问题Dijkstra求最短路径Word版》由会员分享，可在线阅读，更多相关《公园景点导游问题Dijkstra求最短路径Word版（16页珍藏版）》请在金锄头文库上搜索。
1、传播优秀Word版文档 ，希望对您有帮助，可双击去除！公园主要游览景点导游问题。问题描述：对某公园主要游览景点导游。功能需求：要求完成以下功能：1.将公园内各景点输出。2.将公园内每两个位置（若两个位置之间有直接路径）的距离输出。3.修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；4.求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径；5.删除：删除任意一条边。6.插入：插入任意一条边。代码#include #include #include #include #include #includ
2、e #define MAX 1000#define LENGTH 6#define value int typedef struct char name30; int num; VEXTYPE; typedef struct VEXTYPE vexsLENGTH; value arcsLENGTHLENGTH; int vexnum,arcnum ; MGraph;MGraph b; MGraph InitGraph() int i, j; MGraph G;G.vexnum =6; /初始景点数为6，即图的顶点数G.arcnum =15; /初始景点最大路径数为15 ，即图的最大边数for(
3、i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.vexs0.name,景点A); /景点Astrcpy(G.vexs1.name,景点B); /景点Bstrcpy(G.vexs2.name,景点C); /景点Cstrcpy(G.vexs3.name,景点D); /景点Dstrcpy(G.vexs4.name,景点E); /景点Estrcpy(G.vexs5.name,景点F); /景点Ffor(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=MAX;G.arcs01=50; /景点A与景点B的距离为 50G.
4、arcs02=20; /景点A与景点C的距离为 20G.arcs03=30; /景点A与景点D的距离为 30G.arcs12=10; /景点B与景点C的距离为 10G.arcs14=70; /景点B与景点E的距离为 70G.arcs25=90; /景点C与景点F的距离为 90G.arcs35=40; /景点D与景点F的距离为 40G.arcs45=50; /景点E与景点F的距离为 50for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij;return G;void Menu() /功能需求选项菜单 cout*功能需求选项菜单
5、*n; cout 1-输出公园内景点n; cout 2-输出每两个直接相连景点的距离n; cout 3-修改两个景点距离n; cout 4-两景点之间最短路径n; cout 5-删除某条边（两个直接相连景点的连线）n; cout 6-插入某条边n; cout 0-退出n; cout*某公园主要游览景点导游*n; void PutOutVex(MGraph *G) /功能 1 输出公园内景点cout公园内各景点endl;for(int i=0;ivexnum;i+)coutvexsi.name endl; void PutOutArc(MGraph *G) /功能 2 输出公园内每两个直接相连景
6、点的距离for(int i=0;ivexnum;i+) for(int j=0;jvexnum;j+) if(G-arcsijMAX) cout vexsi.namevexsj.name的距离为 arcsijendl; void Change(MGraph *G) /功能 3 修改：修改两个景点距离（权值） int v0,v1,length; coutv0; cinv1; coutlength; G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /功能 4.求最短路径 输出给定两景点之间的最短路径的长度及途经的各景点 /使用Dijks
7、tra算法求解最短路径 int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; coutv0; if(v0G-vexnum) coutv0; coutv1; if(v1G-vexnum) coutv1; for(v=0;vvexnum;v+) finalv=0; Dv=G-arcsv0v; for(w=0;wvexnum;w+) pvw=0; if(DvMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=MAX; for(w=0;wvexnum;w+) if(!finalw) i
8、f(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvwarcsvw; for(x=0;xvexnum;x+) pwx=pvx; pww=1; cout从vexsv0.name到vexsv1.name的最短路径长度为：Dv1endl; cout途经的景点：endl; for(int j=0;jvexnum;j+) if(pv1j=1) coutvexsj.nameendl; void DeleteArc(MGraph *G) /功能 5 删除：删除任意一条边。 int v0,v1; coutv0v1;
9、G-arcsv0v1=MAX; G-arcsv1v0=MAX;void InsertArc(MGraph *G) /功能 6 插入：插入任意一条边。 int v0,v1,l=0; coutv0v1; coutl; G-arcsv0v1=l; G-arcsv1v0=l;void main() int a; b=InitGraph(); Menu(); cina; while(a!=0) switch(a) case 1:PutOutVex(&b);Menu();break; case 2:PutOutArc(&b);Menu();break; case 3:Change(&b);Menu();b
10、reak; case 4:Dijkstra(&b);Menu();break; case 5:DeleteArc(&b);Menu();break; case 6:InsertArc(&b);Menu();break; case 0:exit(1);break; default:break; cina; 附录; 截图菜单显示功能1 输出公园内景点功能2 输出每两个直接相连景点的距离功能4 两景点B F之间最短路径功能3 修改两个景点D F距离,并显示修改结果（截图中景点D景点F距离为60）功能 5删除B C边并显示结果（截图中无景点B-景点C的直接距离）功能 6 插入A F边并显示结果（截图中景点A与景点F之间距离为100）
