公園景點導(dǎo)游問題Dijkstra求最短路徑.doc

公園主要游覽景點導(dǎo)游問題。問題描述：對某公園主要游覽景點導(dǎo)游。功能需求：要求完成以下功能：1.將公園內(nèi)各景點輸出。2.將公園內(nèi)每兩個位置（若兩個位置之間有直接路徑）的距離輸出。3.修改：修改兩個位置（若兩個位置之間有直接路徑）的距離，并重新輸出每兩個位置（若兩個位置之間有直接路徑）的距離；4.求最短路徑：輸出給定兩點之間的最短路徑的長度及途經(jīng)的地點，輸出任意一點與其他各點的最短路徑；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; /初始景點數(shù)為6，即圖的頂點數(shù)G.arcnum =15; /初始景點最大路徑數(shù)為15 ，即圖的最大邊數(shù)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èi)景點n; cout 2-輸出每兩個直接相連景點的距離n; cout 3-修改兩個景點距離n; cout 4-兩景點之間最短路徑n; cout 5-刪除某條邊（兩個直接相連景點的連線）n; cout 6-插入某條邊n; cout 0-退出n; cout*某公園主要游覽景點導(dǎo)游*n; void PutOutVex(MGraph *G) /功能 1 輸出公園內(nèi)景點cout公園內(nèi)各景點endl;for(int i=0;ivexnum;i+) endl; void PutOutArc(MGraph *G) /功能 2 輸出公園內(nèi)每兩個直接相連景點的距離for(int i=0;ivexnum;i+) for(int j=0;jvexnum;j+) if(G-arcsijMAX) cout 的距離為 arcsijendl; void Change(MGraph *G) /功能 3 修改：修改兩個景點距離（權(quán)值） int v0,v1,length; coutv0; cinv1; coutlength; G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /功能 4.求最短路徑 輸出給定兩景點之間的最短路徑的長度及途經(jīng)的各景點 /使用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途經(jīng)的景點：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