公園景點(diǎn)導(dǎo)游問題Dijkstra求最短路徑Word版

1、傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！公園主要游覽景點(diǎn)導(dǎo)游問題。問題描述：對某公園主要游覽景點(diǎn)導(dǎo)游。功能需求：要求完成以下功能：1.將公園內(nèi)各景點(diǎn)輸出。2.將公園內(nèi)每兩個位置（若兩個位置之間有直接路徑）的距離輸出。3.修改：修改兩個位置（若兩個位置之間有直接路徑）的距離，并重新輸出每兩個位置（若兩個位置之間有直接路徑）的距離；4.求最短路徑：輸出給定兩點(diǎn)之間的最短路徑的長度及途經(jīng)的地點(diǎn)，輸出任意一點(diǎn)與其他各點(diǎn)的最短路徑；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; /初始景點(diǎn)數(shù)為6，即圖的頂點(diǎn)數(shù)G.arcnum =15; /初始景點(diǎn)最大路徑數(shù)為15 ，即圖的最大邊數(shù)for(

3、i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,景點(diǎn)A); /景點(diǎn)Astrcpy(G.,景點(diǎn)B); /景點(diǎn)Bstrcpy(G.,景點(diǎn)C); /景點(diǎn)Cstrcpy(G.,景點(diǎn)D); /景點(diǎn)Dstrcpy(G.,景點(diǎn)E); /景點(diǎn)Estrcpy(G.,景點(diǎn)F); /景點(diǎn)Ffor(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=MAX;G.arcs01=50; /景點(diǎn)A與景點(diǎn)B的距離為 50G.

4、arcs02=20; /景點(diǎn)A與景點(diǎn)C的距離為 20G.arcs03=30; /景點(diǎn)A與景點(diǎn)D的距離為 30G.arcs12=10; /景點(diǎn)B與景點(diǎn)C的距離為 10G.arcs14=70; /景點(diǎn)B與景點(diǎn)E的距離為 70G.arcs25=90; /景點(diǎn)C與景點(diǎn)F的距離為 90G.arcs35=40; /景點(diǎn)D與景點(diǎn)F的距離為 40G.arcs45=50; /景點(diǎn)E與景點(diǎn)F的距離為 50for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij;return G;void Menu() /功能需求選項(xiàng)菜單 cout*功能需求選項(xiàng)菜單

5、*n; cout 1-輸出公園內(nèi)景點(diǎn)n; cout 2-輸出每兩個直接相連景點(diǎn)的距離n; cout 3-修改兩個景點(diǎn)距離n; cout 4-兩景點(diǎn)之間最短路徑n; cout 5-刪除某條邊（兩個直接相連景點(diǎn)的連線）n; cout 6-插入某條邊n; cout 0-退出n; cout*某公園主要游覽景點(diǎn)導(dǎo)游*n; void PutOutVex(MGraph *G) /功能 1 輸出公園內(nèi)景點(diǎn)cout公園內(nèi)各景點(diǎn)endl;for(int i=0;ivexnum;i+) endl; void PutOutArc(MGraph *G) /功能 2 輸出公園內(nèi)每兩個直接相連景

6、點(diǎn)的距離for(int i=0;ivexnum;i+) for(int j=0;jvexnum;j+) if(G-arcsijMAX) cout 的距離為 arcsijendl; void Change(MGraph *G) /功能 3 修改：修改兩個景點(diǎn)距離（權(quán)值） int v0,v1,length; coutv0; cinv1; coutlength; G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /功能 4.求最短路徑 輸出給定兩景點(diǎn)之間的最短路徑的長度及途經(jīng)的各景點(diǎn) /使用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從到的最短路徑長度為：Dv1endl; cout途經(jīng)的景點(diǎn)：endl; for(int j=0;jvexnum;j+) if(pv1j=1) endl; 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();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