【文章內(nèi)容簡(jiǎn)介】 [w]) { dist[w]=dist[u]+Edge[u][w]。 path[w]=u。 } } 故宮導(dǎo)游咨詢 13 for( i=0。inumV。i++) { if(i!=vamp。amp。dist[i]!=MAXweight) { string c[10]。 int j=0。 int k=i。 cout從 b到 Vertices[i].dingdian的 。 cout最佳路徑長(zhǎng)度為 :。 coutdist[i]米 。 cout大約需要走 dist[i]/100分鐘 。 cout路徑為 :。 do{ j++。 c[j]=Vertices[k].dingdian。 k=path[k]。 } while(k!=v)。 j++。 c[j]=Vertices[k].dingdian。 for(int n=j。n=1。n) { coutc[n]。 if(n!=1) cout。 } coutendl。 } } 故宮導(dǎo)游咨詢 14 } 求到所有景點(diǎn)的路徑 void Graph::shortpath2() { int v。 string b。 cout輸入你所在的景點(diǎn) :。 cinb。 for(int i=0。inumV。i++) if(Vertices[i].dingdian==b) v=i。 for( i=0。inumV。i++) { dist[i]=Edge[v][i]。 s[i]=0。 if(i!=vamp。amp。dist[i]MAXweight) path[i]=v。 else path[i]=1。 } s[v]=1。 dist[v]=0。 for(i=0。inumV。i++) { float min=MAXweight。 int u=v。 for(int j=0。jnumV。j++) if(!s[j]amp。amp。dist[j]min) { u=j。 故宮導(dǎo)游咨詢 15 min=dist[j]。 } s[u]=1。 for(int w=0。wnumV。w++) if(!s[w]amp。amp。Edge[u][w]MAXweightamp。amp。dist[u]+Edge[u][w]dist[w]) { dist[w]=dist[u]+Edge[u][w]。 path[w]=u。 } } for( i=0。inumV。i++) { if(i!=vamp。amp。dist[i]!=MAXweight) { string c[10]。 int j=0。 int k=i。 cout從 b到 Vertices[i].dingdian的 。 cout最佳路徑長(zhǎng)度為 :。 coutdist[i]米 。 cout大約需要走 dist[i]/100分鐘 。 cout路徑為 :。 do{ j++。 c[j]=Vertices[k].dingdian。 k=path[k]。 } while(k!=v)。 j++。 c[j]=Vertices[k].dingdian。 故宮導(dǎo)游咨詢 16 for(int n=j。n=1。n) { coutc[n]。 if(n!=1) cout。 } coutendl。 } } } 主函數(shù) void main() { Graph a。 for(。) { char c。 system(cls)。 cout******************************endl。 cout****** 登錄 ! ******endl。 cout******************************endl。 cout****** A、管理員 ******endl。 cout****** B、游客 ******endl。 cout****** C、退出 ******endl。 cout****** 請(qǐng)選擇 (A、 B、 C)******endl。 cout******************************endl。 cinc。 if(c==39。A39。) { 故宮導(dǎo)游咨詢 17 int d。 char b。 cout請(qǐng)輸入密碼 :。 cind。 if(d==123) { for(。) { system(cls)。 cout********************************endl。 cout*** 歡迎登陸故宮管理系統(tǒng) ***endl。 cout********************************endl。 cout*** A、錄入景點(diǎn)和路徑信息 ***endl。 cout*** B、修改景點(diǎn)信息 ***endl。 cout*** C、插入景點(diǎn)和路徑 ***endl。 cout*** D、刪除景點(diǎn)和路徑 ***endl。 cout*** E、退出 ***endl。 cout*** 請(qǐng)選擇 (A、 B、 C、 D、 E) ***endl。 cout********************************endl。 cinb。 if(b==39。A39。) { ()。 system(pause)。 } if(b==39。B39。) { ()。 system(pause)。 } 故宮導(dǎo)游咨詢 18 if(b==39。C39。) { ()。 system(pause)。 } if(b==39。D39。) { ()。 system(pause)。 } if(b==39。E39。) break。 } } else { cout密碼錯(cuò)誤 !endl。 system(pause)。 } } if(c==39。B39。) { char b。 for(。) { system(cls)。 cout*************************************endl。 cout*** 歡迎登陸故宮導(dǎo)游系統(tǒng) ***endl。 故宮導(dǎo)游咨詢 19 cout*************************************endl。 cout*** A、查詢信息 ***endl。 cout*** B、查詢到景點(diǎn)的最佳路徑 ***endl。 cout*** C、查詢到所有景點(diǎn)的最佳路徑 ***endl。 cout*** D、退出 ***endl。 cout*** 請(qǐng)選擇 (A、 B、 C、 D) ***endl。 cout*************************************endl。 cinb。 if(b==39。A39。) { ()。 system(pause)。 } if(b==39。B39。) { ()。 system(pause)。 } if(b==39。C39。) { ()。 system(pause)。 } if(b==39。D39。) break。 } } if(c==39。C39。) break。 } 故宮導(dǎo)游咨詢 20 } 4 調(diào)試分析 測(cè)試數(shù)據(jù) 測(cè)試數(shù)據(jù)見(jiàn)圖 1. 調(diào)試問(wèn)題 在調(diào)試過(guò)程中遇到輸出路徑算法有錯(cuò)誤，當(dāng)刪除一條路徑時(shí)時(shí)不能正確輸出相應(yīng)路徑，然后對(duì)輸出路徑的條件進(jìn)行改進(jìn)，增加了條件，測(cè)試成功。 算法時(shí)間復(fù)雜度 錄入：時(shí)間復(fù)雜度為 O(n)。 查詢景點(diǎn)信息 : 時(shí)間復(fù)雜度為 O(n)。 修改景點(diǎn)信息 : 時(shí)間復(fù)雜度為 O(n)。 插入景點(diǎn)和路徑 : 當(dāng)插入的景 點(diǎn)和路徑為 x， y 時(shí)，若 x=y 時(shí)間復(fù)雜度為 O(x)反之為 O(y)。 刪除景點(diǎn)和路徑 : 當(dāng)刪除的景點(diǎn)和路徑為 x， y 時(shí)，若 x=y 時(shí)間復(fù)雜度為 O(x)反之為 O(y)。 查詢到某景點(diǎn)最佳路徑； 此算法為迪杰斯特拉算法 時(shí)間復(fù)雜度為 O(n*n)。 查詢到所有景點(diǎn)的最短路徑 : 此算法為迪杰斯特拉算法時(shí)間復(fù)雜度為 O(n*n)。 經(jīng)驗(yàn)和體會(huì) 在本次課程設(shè)計(jì)中主要是對(duì)圖的數(shù)據(jù)結(jié)構(gòu)操作，所有剛開(kāi)始對(duì)知識(shí)不是很熟悉操作起來(lái)有一定難度，容易在程序的關(guān)鍵地方但經(jīng)過(guò)翻閱教材能較好的解決問(wèn)題 。 5 用戶使用說(shuō)明 本系統(tǒng)是關(guān)于故宮的管理 系統(tǒng)分為兩類用戶，管理員和游客， 由于