公園的導(dǎo)游圖

1、 用C+語(yǔ)言設(shè)計(jì)一個(gè)公園的導(dǎo)游圖 第26頁(yè) 共26頁(yè) 用C+語(yǔ)言設(shè)計(jì)一個(gè)公園的導(dǎo)游圖摘 要 現(xiàn)實(shí)生活中，常常會(huì)遇到求最短路徑的問(wèn)題。本課程設(shè)計(jì)旨在提供一種解決這類問(wèn)題的實(shí)例，把某一公園的景點(diǎn)與路線抽象成頂點(diǎn)和邊，從而構(gòu)成圖，進(jìn)而解決一系列相關(guān)的最短路徑，最佳路線等問(wèn)題。在課程設(shè)計(jì)中，系統(tǒng)開發(fā)平臺(tái)為Windows XP，程序設(shè)計(jì)設(shè)計(jì)語(yǔ)言采用C+，程序運(yùn)行平臺(tái)為Windows 98/2000/XP。對(duì)于求解最短路徑，使用了著名的Dijkstra算法。對(duì)于求最佳路徑，采用了常用于解決TSP問(wèn)題的貪心法。程序通過(guò)調(diào)試運(yùn)行，初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)，并且經(jīng)過(guò)適當(dāng)完善后，這一導(dǎo)游圖系統(tǒng)將同樣適用于其他公園。關(guān)鍵

2、詞 程序設(shè)計(jì)；數(shù)據(jù)結(jié)構(gòu)；圖；最短路徑；Dijkstra算法；TSP問(wèn)題1 引 言現(xiàn)實(shí)生活中，常常會(huì)遇到求最短路徑的問(wèn)題，本課程設(shè)計(jì)將把這類問(wèn)題實(shí)例化，把一個(gè)公園的景點(diǎn)頂點(diǎn)化、路徑邊化，建成一個(gè)圖，再通過(guò)比較對(duì)圖中各邊及頂點(diǎn)的關(guān)系，實(shí)現(xiàn)對(duì)公園各個(gè)景點(diǎn)進(jìn)行訪問(wèn)，并能根據(jù)要求，求出任意兩個(gè)頂點(diǎn)的最短路徑，還能給出一條依次不重復(fù)訪問(wèn)各點(diǎn)的最短路徑?！具@部分應(yīng)寫明前人相關(guān)的研究成果、理論與實(shí)踐依據(jù)，內(nèi)容可包括研究的目的、意義、主要方法、范圍和背景等?！侩S著計(jì)算機(jī)科學(xué)的迅速發(fā)展，計(jì)算機(jī)已深入到揉社會(huì)的各個(gè)領(lǐng)域，它的應(yīng)用已不再局限于科學(xué)計(jì)算，以解決一些數(shù)學(xué)問(wèn)題，而且可以解決一些抽象化的具體問(wèn)題，更多地用于控

3、制，管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作，這便為我們的日常生活提供了很多的方便，譬如說(shuō)火車售票系統(tǒng)，學(xué)生成績(jī)管理，車廂調(diào)度等實(shí)際問(wèn)題。如今程序設(shè)計(jì)的語(yǔ)言很多，有發(fā)展比較完善高級(jí)語(yǔ)言，也有最基本的低級(jí)語(yǔ)言，然而再好的程序設(shè)計(jì)也要有一個(gè)比較清晰的思路算法。為了編寫好一個(gè)好程序，必須分析待處理對(duì)象的特性以及各處理對(duì)象之間的關(guān)系，于是數(shù)據(jù)結(jié)構(gòu)便成為我們絕佳的選擇。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核心課程，而且已成為其他理工專業(yè)的熱門選修課。2程序的功能需求分析2. 1 程序的功能分析一個(gè)公園的導(dǎo)游圖，至少應(yīng)該有一個(gè)簡(jiǎn)單的景點(diǎn)分布圖，讓游客能對(duì)公園概況一目了然。其次，應(yīng)該

4、能提供相關(guān)的景點(diǎn)信息：包括景點(diǎn)名稱，景點(diǎn)簡(jiǎn)介等。以上功能是基礎(chǔ)，在此基礎(chǔ)上，使公園的導(dǎo)游圖系統(tǒng)更具人性化，更具有實(shí)用性：為導(dǎo)游圖系統(tǒng)添加景點(diǎn)最短路徑的計(jì)算，提供依次不重復(fù)訪問(wèn)所有景點(diǎn)的最佳旅游路線。2.2 菜單項(xiàng)及其基本操作擁有了完整的功能的導(dǎo)游圖系統(tǒng)，還需要有清爽，簡(jiǎn)易的操作界面，讓游客一目了然，操作方便。本導(dǎo)游圖用數(shù)字鍵的選擇方式，加以提示，提供給用戶如圖2.1的簡(jiǎn)單方便的操作。圖2.1 抽象化的公園導(dǎo)游圖至此，已經(jīng)規(guī)劃好導(dǎo)游圖系統(tǒng)的功能和操作的基本構(gòu)架，下一步就是著手為每一個(gè)操作的實(shí)現(xiàn)做程序?qū)崿F(xiàn)的考慮了。3 程序的算法分析要完成對(duì)整個(gè)導(dǎo)游圖系統(tǒng)的功能實(shí)現(xiàn)，需要對(duì)的每一項(xiàng)功能都有清楚的設(shè)想

5、和認(rèn)識(shí)，了解并明確每一項(xiàng)功能的實(shí)現(xiàn)需要解決的問(wèn)題，選擇正確并且高效的算法把問(wèn)題逐個(gè)解決，最終實(shí)現(xiàn)程序的正確調(diào)試運(yùn)行。為此，可把系統(tǒng)分為以下幾個(gè)核心：圖的初始化、圖的遍歷、求兩點(diǎn)間的最短路徑、求最佳路線。3.1 圖的初始化圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，表現(xiàn)在不僅各個(gè)頂點(diǎn)的度可以相差很多，而且頂點(diǎn)之間的邏輯關(guān)系鄰接關(guān)系也錯(cuò)綜復(fù)雜1。從圖的定義可知，一個(gè)圖包括兩部分信息：頂點(diǎn)的信息以及描述頂點(diǎn)之間關(guān)系（邊或?。┑男畔?。圖的初始化是所有相關(guān)操作的基礎(chǔ)，其存儲(chǔ)結(jié)構(gòu)將直接影響到程序的實(shí)現(xiàn)的難易度、空間性能和時(shí)間性能，因此選擇適合本次程序的存儲(chǔ)結(jié)構(gòu)至關(guān)重要。圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表、邊

6、集數(shù)組等多種，較常用的有鄰接矩陣和鄰接表，而這兩者的存儲(chǔ)方式的比較如表3-1。表3-1 鄰接矩陣與鄰接表存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)方式空間性能比較時(shí)間性能比較唯一性比較鄰接矩陣O(n2)O(n2)唯一鄰接表O(n+e)O(n+e)非唯一圖的鄰接矩陣和鄰接表存儲(chǔ)各有利弊，應(yīng)用時(shí)要根據(jù)圖的稠密和稀疏程度以及問(wèn)題的需求進(jìn)行選擇2。仔細(xì)比較這兩種存儲(chǔ)方式容易知道，由于鄰接矩陣特殊的存儲(chǔ)方式，如圖2.2所示，它非常便于快速的查找兩個(gè)頂點(diǎn)之間的邊上的權(quán)值。所以，圖采用帶權(quán)的鄰接矩陣存儲(chǔ)。V2V1V4V3V04375792Vertex5 =V0V1V2V3V495734Arc55=937254772圖3.1 無(wú)向圖

7、及其鄰接矩陣存儲(chǔ)示意圖決定了圖的存儲(chǔ)方式后，需要有一個(gè)公園的實(shí)例，本程序選擇本人所在地的姑婆山國(guó)家森林公園的游覽地圖作為藍(lán)本，把公園地圖抽象化成頂點(diǎn)與邊構(gòu)成的圖形式，如圖3.2，途中紅色數(shù)字代表線的權(quán)值。150346725132432413223圖3.2 抽象化的公園導(dǎo)游圖3.2 圖的遍歷圖的遍歷是圖中最基本的操作。圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)，對(duì)圖中所有頂點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。導(dǎo)游圖需要把每條路徑的信息都向游客展示，就需要讀取每?jī)蓚€(gè)頂點(diǎn)間的路徑信息。由于采用了帶權(quán)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，所以需要針對(duì)這一存儲(chǔ)結(jié)構(gòu)對(duì)路線進(jìn)行遍歷操作。其遍歷算法如圖3.3所示，執(zhí)行效果如圖3.4所示。選擇

8、圖片控件For循環(huán)語(yǔ)句（i=0；i<頂點(diǎn)數(shù)；i+）NFor循環(huán)語(yǔ)句(j=0;j<i;j+)YYNY開始結(jié)束如果路徑存在輸出該路徑信息N圖3.3 圖的遍歷算法流程圖第一次循環(huán)第二次循環(huán)第三次循環(huán)第四次循環(huán)V2V1V4V3V04375792 圖3.4 圖的遍歷算法執(zhí)行效果示意圖3.3 最短路徑（Dijkstra算法）基于本程序中圖的存儲(chǔ)是鄰接矩陣結(jié)構(gòu)存儲(chǔ)的圖結(jié)構(gòu)，因而采用適合該存儲(chǔ)結(jié)構(gòu)的Dijkstra算法用于解決求最短路徑的問(wèn)題。迪杰斯特拉（Dijkstra）提出了一個(gè)按路徑長(zhǎng)度遞增的持續(xù)產(chǎn)生最短路徑的算法，其基本思想是：設(shè)置一個(gè)集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源

9、點(diǎn)v，對(duì)于viV-S，假設(shè)從源點(diǎn)v到vi的有向邊為最短路徑。以后每求得一條最短路徑v，vk，就將vk加入集合S中，并將路徑v，vk，vi，與原來(lái)的假設(shè)相比較，取路徑長(zhǎng)度較小者為最短路徑。重復(fù)上述過(guò)程，直到集合V中全部頂點(diǎn)加入到集合S中。如圖3.5所示。集合S集合V-SVVkVi圖3.5 圖的遍歷算法執(zhí)行效果示意圖輔助數(shù)組distn：元素disti表示當(dāng)前找到的從源點(diǎn)到終點(diǎn)vi的最短路徑的長(zhǎng)度。初態(tài)為:若從v到vi有弧，則disti為弧上的權(quán)值；否則置disti為。若當(dāng)前求得的終點(diǎn)為vk,則根據(jù)下式進(jìn)行迭代：disti=mindisti,distk+arcki 1in輔助數(shù)組pathn:元素pa

10、thi是一個(gè)串，表示當(dāng)前所找到的從源點(diǎn)到終點(diǎn)vi的最短路徑。初態(tài)為：若從v到vi有弧，則pathi為“vvk”，否則置pathi為空串。數(shù)組sn：存放源點(diǎn)和已經(jīng)生成的終點(diǎn)（即集合S），初態(tài)為只有一個(gè)源點(diǎn)v。算法的偽代碼描述是：1.初始化數(shù)組dist、path和s；2.while（s中的元素個(gè)數(shù)<n）2.1 在distn中求最小值，其下標(biāo)為k（則vk為正在生成的終點(diǎn)）；2.2 輸出distj和pathj；2.3 修改數(shù)組dist和path;2.4 將頂點(diǎn)vk添加到數(shù)組s中；3.4 最佳訪問(wèn)路線（貪心法）在解決最佳訪問(wèn)路線問(wèn)題時(shí)，不得不提到TSP問(wèn)題。所謂的TSP問(wèn)題就是指旅行家要旅行n個(gè)城

11、市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短，最后返回到出發(fā)點(diǎn)。該這個(gè)又稱貨郎擔(dān)問(wèn)題、郵遞員問(wèn)題，是圖問(wèn)題中最廣為人知的問(wèn)題。對(duì)于TSP問(wèn)題，一種最容易想到，也肯定能得到最佳解的算法是窮舉法，即考慮所有可能的旅游路線，從中選擇最佳的一條。但是用窮舉法求解TSP問(wèn)題的時(shí)間復(fù)雜度為O（n?。?，當(dāng)n大到一定程度后是不可解的3。在這里就引出解決此問(wèn)題的一個(gè)經(jīng)典算法：貪心法。貪心法（ Greedy algorithm ，直譯：貪心算法） 是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。比如在旅行推銷員問(wèn)題中，如果旅行員每次都選擇最近的城市

12、，那這就是一種貪心算法4。因此貪心法非常適合程序的最佳旅游路徑的求解。貪心法可以解決一些最優(yōu)性問(wèn)題，如：求圖中的最小生成樹、求哈夫曼編碼對(duì)于其他問(wèn)題，貪心法一般不能得到我們所要求的答案。一旦一個(gè)問(wèn)題可以通過(guò)貪心法來(lái)解決，那么貪心法一般是解決這個(gè)問(wèn)題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果，貪心法也可以用作輔助算法或者直接解決一些要求結(jié)果不特別精確的問(wèn)題。對(duì)于大部分的問(wèn)題，貪心法通常(但不一定)都不能找出最佳解, 因?yàn)樗麄円话銢]有測(cè)試所有可能的解。貪心法容易過(guò)早做決定, 因而沒法達(dá)到最佳解。然而，貪心法的好處在于容易設(shè)計(jì)和很多時(shí)能達(dá)到好的近似解5。本程序的最佳路線問(wèn)題的解

13、決辦法，就采用這種求近似最優(yōu)解的算法。貪心法算法用偽代碼描述如下：1.任意選擇某個(gè)頂點(diǎn)v作為出發(fā)點(diǎn)；2.執(zhí)行下述過(guò)程，直到所有點(diǎn)都被訪問(wèn)：v= 最后一個(gè)被訪問(wèn)的頂點(diǎn)； 在頂點(diǎn)v的鄰接點(diǎn)中查找距離頂點(diǎn)v最近的未被訪問(wèn)的鄰接點(diǎn)j； 訪問(wèn)頂點(diǎn)j；3.從最后一個(gè)訪問(wèn)的頂點(diǎn)回到出發(fā)點(diǎn)v；以圖3.2為導(dǎo)游圖系統(tǒng)實(shí)例代入后，最佳路線的算法按照如圖3.6所示的方式進(jìn)行圖的頂點(diǎn)遍歷。150346725132432413223最佳路徑長(zhǎng)度：1+5+2+3+2+1+3+2=19最佳路徑：(0)-(1)-(5)-(7)-(3)-(6)-(4)-(2)-(0)圖3.6 實(shí)際最佳路徑及路徑長(zhǎng)度4程序的運(yùn)行與測(cè)試4.1程序

14、運(yùn)行初始界面程序運(yùn)行，后臺(tái)對(duì)圖結(jié)構(gòu)進(jìn)行初始化，運(yùn)行結(jié)果如圖4.1。圖4.1 最短路徑算法正確輸出實(shí)現(xiàn)4.2查看公園地圖公園地圖的查看，輸出用cout語(yǔ)句建立的公園地圖。圖4.2 公園地圖4.3查看路程信息遍歷圖的所有路徑并依次輸出路徑信息。圖4.3 所有邊的信息4.4 求最短路徑根據(jù)用戶要求，求始點(diǎn)到終點(diǎn)的最短路徑信息和所有路徑信息。如圖4.4和4.5所示。圖4.4 兩景點(diǎn)間的最短路徑圖4.5 始發(fā)點(diǎn)到所有景點(diǎn)的最短路徑4.4 求最佳路徑為游客提供一條可以依次不重復(fù)地游覽所有景點(diǎn)并最終回到起點(diǎn)的最短路徑。4.5 退出用break實(shí)現(xiàn)程序退出。5 存在的不足與對(duì)策由于設(shè)計(jì)者水平有限，本導(dǎo)游圖系統(tǒng)

15、的功能還比較簡(jiǎn)單，還有一些好的設(shè)想沒有實(shí)現(xiàn)：比如添加管理模式，使得公園管理人員能夠同樣方便的更改導(dǎo)游圖，因此更改這一導(dǎo)游圖還必須在程序員的幫助下進(jìn)行。另外，本導(dǎo)游圖系統(tǒng)還有一定的局限性，如果存在只有一條通路的景點(diǎn)，導(dǎo)游圖將無(wú)法求得最佳旅游路徑。公園的導(dǎo)游圖系統(tǒng)的這些不足請(qǐng)老師多多諒解。今后我會(huì)更多的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，更深刻地理解圖的基本操作，不斷提升認(rèn)識(shí)，提高編程技巧，借以不斷地提高程序設(shè)計(jì)水平。參考文獻(xiàn)1 朱戰(zhàn)立. 數(shù)據(jù)結(jié)構(gòu)使用C+語(yǔ)言. 西安：西安電子科技大學(xué)出版社，20012王紅梅，胡明，王濤. 數(shù)據(jù)結(jié)構(gòu)(C+版). 北京：清華大學(xué)出版社，20053馬春江，李慧勇，孟繁軍. 新編數(shù)

16、據(jù)結(jié)構(gòu)教程. 北京：中國(guó)電力出版社，20064貪心法_維基百科. 維基百科，/wiki/%E8%B4%AA%E5%BF%83%E6%B3%95：2008-9-045田魯懷. 數(shù)據(jù)結(jié)構(gòu). 北京：電子工業(yè)出版社，2006附錄 A 用C+語(yǔ)言設(shè)計(jì)一個(gè)公園的導(dǎo)游圖/ 程序名稱：ParkGuide.h/ 程序功能：程序的變量及函數(shù)聲明#ifndef PARKGUIDE_H /定義頭文件#define PARKGUIDE_H #include<string> /引入標(biāo)準(zhǔn)庫(kù)中的頭文件using namespace std; const int MaxS

17、ize=12; /圖中最多頂點(diǎn)個(gè)數(shù)template <class T>class ParkGuidepublic: ParkGuide(int* a, T* v,int n); /構(gòu)造函數(shù)，初始化具有n個(gè)頂點(diǎn)的圖 ParkGuide( )  /析構(gòu)函數(shù) void Dijkstra( int v,int endv);/最小距離 void PutOutArcInfo(); /輸出路徑void TSP(int v); /求最優(yōu)路徑private: T vertexMaxSize; /存放圖中頂點(diǎn)的數(shù)組 int arcMaxSizeMaxSize;  /存放圖中邊的數(shù)組

18、 int vertexNum; /圖的頂點(diǎn)數(shù)和邊數(shù) ;#endif/ 程序名稱：ParkGuideMain.cpp/ 程序功能：程序的#include <iostream>#include <string> /引入標(biāo)準(zhǔn)庫(kù)中的頭文件#include "ParkGuide.cpp"    /引用 ParkGuide.cpp 文件#include "TSP.cpp"     /引用解決最佳旅游路線的TSP文件using namespace std;int main(i

19、nt argc, char* argv) const int numv = 8; /頂點(diǎn)數(shù)int control=1;    /控制 int which;  /功能選擇變量string name;  /插入頂點(diǎn)的值int bordernumvnumv=  /按鄰接矩陣確定頂點(diǎn)的權(quán)值10000,1,2,2,10000,10000,10000,10000, /0號(hào)景點(diǎn)1,10000,10000,10000,10000,5,10000,10000,/1號(hào)景點(diǎn)2,10000,10000,3,3,10000,4,10000, /2號(hào)景點(diǎn)2,10000,3

20、,10000,10000,3,2,3, /3號(hào)景點(diǎn)10000,10000,3,10000,10000,10000,1,10000,/4號(hào)景點(diǎn)10000,5,10000,3,10000,10000,5,2, /5號(hào)景點(diǎn)10000,10000,4,2,1,5,10000,4, /6號(hào)景點(diǎn)10000,10000,10000,3,10000,2,4,10000  /7號(hào)景點(diǎn); string vnamenumv="公園正門","牛頭寨","梅園山莊","方家茶園","情人林","獼猴園

21、","仙姑瀑布","仙姑廟" /初始化各頂點(diǎn) int* p; /定義指針pstring* q; /定義指針qp = &border00; /p指針指向cost數(shù)組的起始位置q = vname;  /q指針指向vname數(shù)組ParkGuide<string> g(p, q, numv ); /調(diào)用Graph程序 while ( control=1 ) /控制cout<<" * "<<endl;cout<<" *歡迎您到姑婆山國(guó)家森林公園* "

22、<<endl;cout<<"*"<<endl;cout<<"*請(qǐng)選擇你想要進(jìn)行的操作： *"<<endl;cout<<"*1、查看公園地圖*"<<endl;cout<<"*2、查看路程信息*"<<endl;cout<<"*3、提供游覽景點(diǎn)的最短路徑*"<<endl;cout<<"*4、提供游覽公園的一種最佳路徑*"<<en

23、dl;cout<<"*5、退出*"<<endl;cout<<"*"<<endl; cin >> which; switch( which )  /功能選擇 case 1: /輸出圖的各頂點(diǎn)的值cout<<" 公園地圖 "<<endl;cout<<" <7> 仙姑廟   "<<endl;cout<<" . . .  "<&

24、lt;endl;cout<<" . . .  "<<endl;cout<<" <6> 仙姑瀑布 . <5>獼猴園 "<<endl;cout<<" . . . . . . "<<endl;cout<<" . . . . . . "<<endl;cout<<" <4> 情人林 . . . . . "<<endl;cout<<

25、" . . <3>方家茶園 . "<<endl;cout<<" . . . . . "<<endl;cout<<" . . . . "<<endl;cout<<" <2>梅園山莊 . <1> 牛頭寨 "<<endl;cout<<" . . . "<<endl;cout<<" . . . "<<endl;cout

26、<<" <0> 正 門 "<<endl; break; case 2: /輸出圖中的路徑 int i; int j; cout<<"所有的邊的信息為:"<<"n" try g.PutOutArcInfo(); catch(char*) cout<<"輸出不正確！"<<endl; break; case 3: /求最短路徑 cout<<"請(qǐng)輸入您所在景點(diǎn)序號(hào):"<<"n"

27、 int vv ; cin>>vv; cout<<"請(qǐng)輸入您想到的景點(diǎn)序號(hào)，若要全部顯示請(qǐng)輸入9:"<<"n" int vvt ; cin>>vvt; try g.Dijkstra(vv,vvt); catch(char*) cout<<"輸出頂點(diǎn)不正確！"<<endl; break; case 4: cout<<"本公園為您提供的最佳旅游路線是："<<"n" g.TSP(0); /求最優(yōu)旅游路線 b

28、reak; case 5: /退出 control=0; cout<<""<<endl; cout<<"謝謝使用,祝您旅途愉快!"<<endl; cout<<""<<endl; break; default:cout<<"對(duì)不起，輸入錯(cuò)誤，請(qǐng)重新輸入!"<<endl<<endl<<endl; return 0;/ 程序名稱：ParkGuide.cpp/ 程序功能：完成游戲的初始化、對(duì)鼠標(biāo)響應(yīng)及判斷

29、游戲是否完成功能#include<iostream>#include <string> /引入標(biāo)準(zhǔn)庫(kù)中的頭文件#include "ParkGuide.h" /引入頭文件using namespace std;/* 前置條件：圖不存在 輸入：無(wú) 功能：圖的初始化 輸出：無(wú) 后置條件：構(gòu)造一個(gè)有值的圖*/template <class T>ParkGuide<T>:ParkGuide(int* a,T* v, int n ) /構(gòu)造圖 int i,j; vertexNum=n; /頂點(diǎn)數(shù) for (i=0; i<MaxSiz

30、e; i+) /初始化鄰接矩陣 for (j=0; j<MaxSize; j+) /定義邊 arcij = 10000; for ( i=0; i<vertexNum; i+) vertexi=vi; /存儲(chǔ)頂點(diǎn)信息 for (i=0; i<vertexNum; i+) /給邊賦置 for (j=0; j<vertexNum; j+) arcij=*(a+i*n+j); int tt=0; /* 前置條件：圖已存在 輸入：無(wú) 功能：輸出圖中所有的路徑 輸出：圖中所有頂點(diǎn)的數(shù)據(jù)信息 后置條件：圖保持不變*/template <class T>void Park

31、Guide<T>:PutOutArcInfo() /輸出圖中所有的路徑 int i=0; /假設(shè)源點(diǎn)是第0個(gè)頂點(diǎn)，即頂點(diǎn)序號(hào)是0 int j=0;if ( i>vertexNum| j>vertexNum) throw "位置" /錯(cuò)誤拋出異常 else for(i=0;i<vertexNum;i+) /輸出任意兩點(diǎn)之間的路徑 for(j=0;j<i;j+) if(arcij<10000) /兩點(diǎn)之間存在路徑 cout<<"從 "<<vertexi<<" 到 &quo

32、t;<<vertexj<<" 的路程為："<<arcij<<"公里n" /若兩點(diǎn)間有路，則輸出該兩點(diǎn)間的路徑 /* 前置條件：圖已存在 輸入：頂點(diǎn)v ，endv 功能：假如endv存在，求v到endv的最短路徑；假如不輸入endv，則求v到任意頂點(diǎn)的最短路徑 輸出：所求得的最短路徑及所經(jīng)歷的位置 后置條件：圖保持不變*/template <class T>void ParkGuide<T>:Dijkstra(int v,int endv) /求從v頂點(diǎn)到endv點(diǎn)的最短路徑 if (

33、 v>vertexNum) throw "位置" /v頂點(diǎn)或endv頂點(diǎn)輸出不正確則拋出異常 int numv=vertexNum; /頂點(diǎn)數(shù) int distMaxSize; /最短長(zhǎng)度 int pathMaxSize; /當(dāng)前找到的最短路徑 int sMaxSize; /存放源點(diǎn)和已生成的終點(diǎn)的集合 int max= 10000; /代表無(wú)窮大 int i,j,k,wm; for(i=0;i<numv;i+) /按網(wǎng)的鄰接矩陣確定各頂點(diǎn)最短路徑的初值 disti=arcvi; if(i!=v&& disti< max) /如果v、i之間

34、有路 pathi=v; /當(dāng)前找到的最短路徑為v else pathi=-1; /否則v與i頂點(diǎn)不存在路徑 si = 0; /給s集合確定初值0 sv=1;distv=0; /將頂點(diǎn)v本身排除在外 for(k =0;k<numv-1;k+) /求其他numv-1各頂點(diǎn)的最短路徑 wm = max;j=v; /確定當(dāng)前最短路徑wm及頂點(diǎn)的序號(hào)j for( i=0;i<numv;i+) if(!si&&disti<wm) /如果v、i之間有路 j=i;wm = disti; /把當(dāng)前找到的路徑確定為最大值 sj=1; for(i =0;i<numv;i+)

35、/更新未確定最短路徑各頂點(diǎn)的當(dāng)前最短路徑 if(!si&&distj+arcji<disti) /如果v、i兩點(diǎn)的距離加上i、j小于從v點(diǎn)到j(luò)點(diǎn)的距離 disti=distj+arcji;pathi=j; /disti取最小值 if (endv < numv && endv >=0 ) /endv點(diǎn)存在 string mmm="" /初始化字符串 int j =endv; while(j > -1 ) string nnn = vertexj; /依次把頂點(diǎn)存放在nnn字符串中 nnn+=mmm; mmm = &quo

36、t; "+nnn; j = pathj; cout<<"從 "<<vertexv.c_str()<<" 到 "<<vertexendv.c_str()<<" 的最短路程為："<<distendv<<"公里 途經(jīng)："<<mmm.c_str()<<"n"/輸出從v點(diǎn)到endv點(diǎn)的最短路徑 else /endv點(diǎn)不存在for(i=0;i<numv;i+) string mmm=&

37、quot;" /初始化字符串 int j =i; while(j > -1 ) string nnn = vertexj; /依次把頂點(diǎn)存放在nnn字符串中 nnn+=mmm; mmm = " "+nnn; j = pathj; cout<<"從 "<<vertexv.c_str()<<" 到 "<<vertexi.c_str()<<" 的最短路程為："<<disti<<"公里 途經(jīng)："<<mmm.c_str()<<"n"/輸出從v點(diǎn)到任意點(diǎn)的最短路徑 / 程序名稱：TSP.cpp/ 程序功能：解決導(dǎo)游圖的TSP問(wèn)題：求不重復(fù)地訪問(wèn)每一個(gè)并回到起點(diǎn)的最短路徑#include<iostream>#include <string> /引入標(biāo)準(zhǔn)庫(kù)中的頭文件#include "ParkGuide.h" /引入頭文件using namespace std;/* 前置條件：圖已存在 輸入：起點(diǎn) 功能：用貪心法進(jìn)行圖的遍歷 輸出：所求得的最優(yōu)路徑及所經(jīng)歷的位置 后置條件：圖保持不變*