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

公园主要游览景点导游问题。问题描述：对某公园主要游览景点导游。功能需求：要求完成以下功能：1.将公园内各景点输出。2.将公园内每两个位置（若两个位置之间有直接路径）的距离输出。3.修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；4.求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径；5.删除：删除任意一条边。6.插入：插入任意一条边。代码#include #include #include #include #include #include #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(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,景点A); /景点Astrcpy(G.,景点B); /景点Bstrcpy(G.,景点C); /景点Cstrcpy(G.,景点D); /景点Dstrcpy(G.,景点E); /景点Estrcpy(G.,景点F); /景点Ffor(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=MAX;G.arcs01=50; /景点A与景点B的距离为 50G.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*功能需求选项菜单*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+) endl; void PutOutArc(MGraph *G) /功能 2 输出公园内每两个直接相连景点的距离for(int i=0;ivexnum;i+) for(int j=0;jvexnum;j+) if(G-arcsijMAX) cout 的距离为 arcsijendl; void Change(MGraph *G) /功能 3 修改：修改两个景点距离（权值） int v0,v1,length; coutv0; cinv1; coutlength; G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /功能 4.求最短路径 输出给定两景点之间的最短路径的长度及途经的各景点 /使用Dijkstra算法求解最短路径 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) if(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从到的最短路径长度为：Dv1endl; cout途经的景点：endl; for(int j=0;jvexnum;j+) if(pv1j=1) endl; void DeleteArc(MGraph *G) /功能 5 删除：删除任意一条边。 int v0,v1; coutv0v1; 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();break; 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