【文章內容簡介】 [w]) { dist[w]=dist[u]+Edge[u][w]。 path[w]=u。 } } 故宮導游咨詢 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最佳路徑長度為 :。 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。 } } 故宮導游咨詢 14 } 求到所有景點的路徑 void Graph::shortpath2() { int v。 string b。 cout輸入你所在的景點 :。 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。 故宮導游咨詢 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最佳路徑長度為 :。 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。 故宮導游咨詢 16 for(int n=j。n=1。n) { coutc[n]。 if(n!=1) cout。 } coutendl。 } } } 主函數 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****** 請選擇 (A、 B、 C)******endl。 cout******************************endl。 cinc。 if(c==39。A39。) { 故宮導游咨詢 17 int d。 char b。 cout請輸入密碼 :。 cind。 if(d==123) { for(。) { system(cls)。 cout********************************endl。 cout*** 歡迎登陸故宮管理系統(tǒng) ***endl。 cout********************************endl。 cout*** A、錄入景點和路徑信息 ***endl。 cout*** B、修改景點信息 ***endl。 cout*** C、插入景點和路徑 ***endl。 cout*** D、刪除景點和路徑 ***endl。 cout*** E、退出 ***endl。 cout*** 請選擇 (A、 B、 C、 D、 E) ***endl。 cout********************************endl。 cinb。 if(b==39。A39。) { ()。 system(pause)。 } if(b==39。B39。) { ()。 system(pause)。 } 故宮導游咨詢 18 if(b==39。C39。) { ()。 system(pause)。 } if(b==39。D39。) { ()。 system(pause)。 } if(b==39。E39。) break。 } } else { cout密碼錯誤 !endl。 system(pause)。 } } if(c==39。B39。) { char b。 for(。) { system(cls)。 cout*************************************endl。 cout*** 歡迎登陸故宮導游系統(tǒng) ***endl。 故宮導游咨詢 19 cout*************************************endl。 cout*** A、查詢信息 ***endl。 cout*** B、查詢到景點的最佳路徑 ***endl。 cout*** C、查詢到所有景點的最佳路徑 ***endl。 cout*** D、退出 ***endl。 cout*** 請選擇 (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。 } 故宮導游咨詢 20 } 4 調試分析 測試數據 測試數據見圖 1. 調試問題 在調試過程中遇到輸出路徑算法有錯誤，當刪除一條路徑時時不能正確輸出相應路徑，然后對輸出路徑的條件進行改進，增加了條件，測試成功。 算法時間復雜度 錄入：時間復雜度為 O(n)。 查詢景點信息 : 時間復雜度為 O(n)。 修改景點信息 : 時間復雜度為 O(n)。 插入景點和路徑 : 當插入的景 點和路徑為 x， y 時，若 x=y 時間復雜度為 O(x)反之為 O(y)。 刪除景點和路徑 : 當刪除的景點和路徑為 x， y 時，若 x=y 時間復雜度為 O(x)反之為 O(y)。 查詢到某景點最佳路徑； 此算法為迪杰斯特拉算法 時間復雜度為 O(n*n)。 查詢到所有景點的最短路徑 : 此算法為迪杰斯特拉算法時間復雜度為 O(n*n)。 經驗和體會 在本次課程設計中主要是對圖的數據結構操作，所有剛開始對知識不是很熟悉操作起來有一定難度，容易在程序的關鍵地方但經過翻閱教材能較好的解決問題 。 5 用戶使用說明 本系統(tǒng)是關于故宮的管理 系統(tǒng)分為兩類用戶，管理員和游客， 由于