1、 參賽隊(duì)編號： 244 賽題類型代碼： B 無向圖最優(yōu)路徑摘 要：在實(shí)際生活中，我們經(jīng)常會(huì)遇到“最優(yōu)路徑”問題，例如，城市之間的最短線路，或者城市之間最節(jié)省的交通費(fèi)用等問題都屬于該類問題。同樣，在自然界也存在著“最優(yōu)路徑”。在復(fù)雜多變的蟻巢中， 螞蟻總是能以最快、最高效的方式游歷在各個(gè)儲(chǔ)藏間，今天，蟻后讓小蟻同學(xué)按照自己特定的要求尋找食物，針對蟻后的要求，我們采用了大量科學(xué)分析方法，并進(jìn)行了反復(fù)驗(yàn)證，我們建立如下的模型：首先對問題進(jìn)行分析，對約束條件逐一列舉、分析實(shí)質(zhì)，必須經(jīng)過N7、N12兩個(gè)點(diǎn)，必須經(jīng)過兩條直線，實(shí)質(zhì)是經(jīng)過四個(gè)點(diǎn)N2、N4、N13、N14，但這四個(gè)點(diǎn)又與前邊兩個(gè)點(diǎn)有所不同，N

2、2和N4要相鄰，N13和N14要相鄰，必須經(jīng)過起始和終止點(diǎn)（針對此處的歧義，在假設(shè)中解決）深入分析可知，若最多經(jīng)過9個(gè)點(diǎn)是無法完成的，因此求次優(yōu)解。其次遍歷所有路徑找到符合約束條件的，遍歷時(shí)使用窮舉法，走遍每一條可以走的路，在過走點(diǎn)數(shù)超過限制的最多點(diǎn)數(shù)或者已經(jīng)走到了終點(diǎn)，是，則停止，判斷這條是否滿足約束條件，滿足則記錄這條路的信息，不滿足什么都不做；否，則繼續(xù)向前走。最后可以找到所有經(jīng)過不超過限制點(diǎn)數(shù)、滿足約束條件的路徑。再計(jì)算每一條符合要求的費(fèi)用（事實(shí)上可以集成到上一步中，但為了模塊獨(dú)立化，利用分而治之思想，在這里將其分開），按照費(fèi)用排序，在所走點(diǎn)數(shù)的基礎(chǔ)上，在費(fèi)用上再做分析，選出最優(yōu)路徑。

3、最后對模型進(jìn)行分析與評價(jià)，以及改進(jìn)與退關(guān)，模型的適用性較強(qiáng)，只要對數(shù)據(jù)稍加改動(dòng)就可以成為求有向圖最佳路徑的模型。關(guān)鍵字：無向圖最優(yōu)路徑，C語言，圖論，算法目錄一、問題重述1二、模型假設(shè)與符號說明22.1 模型假設(shè)22.2 符號說明2三、問題分析23.1整體分析23.2約束條件分析23.3可行性分析2四、模型建立與求解34.1模型準(zhǔn)備34.2模型建立與求解34.2.1確定所有路線表達(dá)式34.2.2 對路徑的篩選44.2.3費(fèi)用分析54.2.4算法設(shè)計(jì)64.2.5模型求解74.3 對模型的檢驗(yàn)7五、模型評價(jià)95.1模型優(yōu)缺點(diǎn)95.1.1模型優(yōu)點(diǎn)105.1.2模型缺點(diǎn)105.2 模型改進(jìn)10參考文獻(xiàn)

4、10附錄11無向圖最優(yōu)路徑模型一、問題重述最強(qiáng)大腦中的收官蜂巢迷宮變態(tài)級挑戰(zhàn)，相信大家都嘆為觀止！最強(qiáng)大腦收官戰(zhàn)打響后，收視率節(jié)節(jié)攀升，就連蟻后也不時(shí)出題難為一下她的子民們。在動(dòng)物世界中，稱得上活地圖的，除了蜜蜂，螞蟻當(dāng)仁不讓。在復(fù)雜多變的蟻巢中， 螞蟻總是能以最快、最高效的方式游歷在各個(gè)儲(chǔ)藏間（存儲(chǔ)食物）。今天，她看完最新一期節(jié)目，又發(fā)布了一項(xiàng)新任務(wù)：小蟻同學(xué)，我需要玉米庫的玉米，再要配點(diǎn)水果，去幫我找來吧。小蟻正準(zhǔn)備出發(fā)，蟻后又說：哎呀，回來，我還沒說完呢，還有若干要求如下：1.小蟻同學(xué)，你需要盡可能以最少的花費(fèi)拿到食物（附件圖中路線上的數(shù)值表示每兩個(gè)儲(chǔ)物間的花費(fèi)）；2.小蟻同學(xué)，你最多只

5、能經(jīng)過9個(gè)儲(chǔ)藏間拿到食物（包含起止兩個(gè)節(jié)點(diǎn)，多次通過同一節(jié)點(diǎn)按重復(fù)次數(shù)計(jì)算）；3.小蟻同學(xué)，你必須經(jīng)過玉米間，水果間（附件圖中標(biāo)綠色節(jié)點(diǎn)）；4.別忘了，食蟻獸也在路上活動(dòng)呢，一旦與食蟻獸相遇，性命危矣！不過小蟻微信群公告已經(jīng)公布了敵人信息（附件圖中標(biāo)紅色路段）；5.最后，千萬別忘了，還有兩段路是必須經(jīng)過的，那里有我準(zhǔn)備的神秘禮物等著你呢(附件圖中標(biāo)綠色路段)。這下小蟻犯難了，這和它們平時(shí)找食物的集體活動(dòng)規(guī)則不一樣嘛,看來這次需要單獨(dú)行動(dòng)了。要怎么選路呢？小蟻經(jīng)過一番苦思冥想，稿紙堆了一摞，啊，終于找到了！親愛的同學(xué)們，你們能否也設(shè)計(jì)一種通用的路徑搜索算法，來應(yīng)對各種搜索限制條件，找到一條最優(yōu)路

6、徑，順利完成蟻后布置的任務(wù)呢？注：1、蟻巢，有若干個(gè)儲(chǔ)藏間（附件圖中圓圈表示），儲(chǔ)藏間之間有諸多路可以到達(dá)(各儲(chǔ)藏間拓?fù)鋱D見附件);2、節(jié)點(diǎn)本身通行無花費(fèi)；3、該圖為無向圖，可以正反兩方向通行，兩方向都會(huì)計(jì)費(fèi)，并且花費(fèi)相同；4、起止節(jié)點(diǎn)分別為附件圖中S點(diǎn)和E點(diǎn)。5、最優(yōu)路徑：即滿足限制條件的路徑。圖1二、模型假設(shè)與符號說明2.1 模型假設(shè)1.因?yàn)轭}目中并未明確給出是否是從起始點(diǎn)開始到達(dá)終止點(diǎn)，即從s到e，為防止歧義、方便計(jì)算，假設(shè)每條路徑都是從起點(diǎn)到終點(diǎn)；2.下文中說到的點(diǎn)或點(diǎn)數(shù)均代表存儲(chǔ)室或存儲(chǔ)室數(shù)量；3.通過圖1各路段關(guān)系，可以假設(shè)，為得到最優(yōu)路徑，不會(huì)再從N1、N2、N3走回起點(diǎn)。2.2

7、 符號說明符號含義N最多經(jīng)過的點(diǎn)的個(gè)數(shù)xn經(jīng)過的第n個(gè)點(diǎn)Pji第j個(gè)集合Pj個(gè)點(diǎn)中的第i的數(shù)值，即將要走向的下一個(gè)點(diǎn)PjiPj第j個(gè)點(diǎn)所有與其相鄰的點(diǎn)的集合APCk和第k個(gè)點(diǎn)相鄰的點(diǎn)的總數(shù)ik走過的第k個(gè)點(diǎn)集合元素的下標(biāo)，從0到APCi-1Fk走第k條路所需要的總費(fèi)用fij從編號為i的點(diǎn)到編號為j的點(diǎn)的費(fèi)用，即表3i行j列對應(yīng)的值表1三、問題分析3.1整體分析題目的總體思路是在各種約束條件下求出一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，最優(yōu)可以說是有兩個(gè)方面：第一是經(jīng)過的儲(chǔ)藏室即經(jīng)過的點(diǎn)最好，題目中給定為9個(gè)，第二是在途中花費(fèi)的費(fèi)用最少。基于以上分析，我們決定建立無向圖最優(yōu)路徑模型，從通過的點(diǎn)數(shù)和費(fèi)用進(jìn)行優(yōu)

8、化。3.2約束條件分析（1）題目中并未明確給出是從起始點(diǎn)到達(dá)終點(diǎn)（即圖中給出的s和e），為了不產(chǎn)生歧義，以及方便計(jì)算，我們在假設(shè)中規(guī)定該路線是從起始點(diǎn)到達(dá)終點(diǎn)（即圖1中給出的s和e）。（2）最多只能經(jīng)過9個(gè)儲(chǔ)藏室（即9個(gè)點(diǎn)）（3）必須經(jīng)過兩條綠色的路線，即必須經(jīng)過N2、N4、N13、N14，并且N2和N3相鄰，N13和N14相鄰。（4）必須經(jīng)過水果間和玉米間，即必須經(jīng)過N7和N12。（5）不能經(jīng)過有食蟻獸的紅色路段，可以有兩種解決辦法，第一：即N11和N12不能相鄰出現(xiàn)，第二：N11和N12之間沒有連線，沒有通路。（6）所有的路都是可以雙向通行的。3.3可行性分析經(jīng)過約束條件的分析，我們發(fā)現(xiàn)，

9、有八個(gè)特殊點(diǎn)（N2、N4、N7、N12、N13、N14、）必須經(jīng)過，那么按照題目要求，只能再選擇一個(gè)非特殊點(diǎn)通過以完成該路徑，通過圖1分析，這顯然是無法完成的，經(jīng)過進(jìn)一步的分析與計(jì)算，我們發(fā)現(xiàn)在滿足以上約束條件的情況下，最少需要通過11個(gè)點(diǎn)才能完成任務(wù)（相關(guān)計(jì)算與證明在4.3.1中給出）。四、模型建立與求解4.1模型準(zhǔn)備影響實(shí)際問題的因素很多，要解決實(shí)際問題就要建立適當(dāng)?shù)哪Ｐ停纫阉媚Ｐ偷拇我蛩睾雎?，否則所得模型會(huì)因?yàn)榻Y(jié)構(gòu)復(fù)雜而失去可解性同時(shí)又不能把與實(shí)質(zhì)相關(guān)的因素忽略掉，而造成所得模型不能夠正確反映實(shí)際情況而失去可靠性。但若是無法取得實(shí)際問題的最優(yōu)解，只能在犧牲次要因素的條件下獲得最優(yōu)

10、近似解。因此要對實(shí)際問題進(jìn)行簡化、確定變量和參數(shù)，并用某些“規(guī)律”建起變量與參數(shù)間的數(shù)學(xué)模型。影響路線選擇因素很多：經(jīng)過儲(chǔ)藏間數(shù)量限制、必經(jīng)節(jié)點(diǎn)與路徑、危險(xiǎn)路徑阻礙、費(fèi)用最少。對于問題中兩種不同決策變量最少節(jié)點(diǎn)與最少花費(fèi)建立兩種模型分別求出在側(cè)重點(diǎn)不同情況下的最優(yōu)解。經(jīng)過以上的問題分析，針對此問題應(yīng)該建立一個(gè)無線圖最優(yōu)路徑模型。4.2模型的建立與求解此模型是要找出從起始點(diǎn)到終點(diǎn)滿足約束條件，并且使得經(jīng)過的點(diǎn)最少、費(fèi)用最少，因此其核心表達(dá)式是一個(gè)由一個(gè)點(diǎn)指向另一個(gè)點(diǎn)的路線。4.2.1 確定所有路線表達(dá)式x0x1 x2 x3 xN-2 xN-1 式（1）0Px0i0Px1i1Px2i2PxN-3i

11、N-2PxN-2iN-1式（2）i0, APC2-1公式說明：式（1）表示從x0到xN-1的所有點(diǎn)，用有向箭頭連起來，表示一條經(jīng)過了N的點(diǎn)的路徑，起始點(diǎn)顯而易見為x0，終點(diǎn)為xN-1。式（2）與式（1）對應(yīng)，Pji對應(yīng)xn，Pji為xn的確定方法。比如此時(shí)走到x2點(diǎn)，那么下一個(gè)點(diǎn)的確定必然與x2有關(guān)，具體由P2集合中的第i（i從0到APC2-1）個(gè)元素確定。第j個(gè)點(diǎn)的編號即對應(yīng)的j、APCi、Pj都在表2中有詳細(xì)列舉。公式意義：從x0開始，遍歷與它相鄰的所有點(diǎn)，并且每個(gè)點(diǎn)都嘗試走，走到下一個(gè)點(diǎn)，同樣遍歷與其相鄰的所有點(diǎn)，重復(fù)上述步驟，直到走到第N個(gè)點(diǎn)（即編號為N-1的點(diǎn)），便不再繼續(xù)走，或者沒

12、有走到第N個(gè)點(diǎn)，而是已經(jīng)走到了終點(diǎn)即e，也不再繼續(xù)走。這樣可以找到所有走過點(diǎn)數(shù)為N或者能到達(dá)終點(diǎn)的路徑。點(diǎn)編號對應(yīng)符號與其相鄰點(diǎn)的總數(shù)列舉相鄰的點(diǎn)01234560P031231P132492P2413453P3425674P4412595P572346910126P6735781213147P733688P846714159P95145101110P10459111211P1139101612P1255610131613P1366121415161714154813141716P1641112131717P1700表2 各節(jié)點(diǎn)信息表4.2.2 對路徑的篩選（添加程序）

13、（1）限制經(jīng)過的最多點(diǎn)數(shù)為了保證程序能夠正常、快速地運(yùn)行，在第一步尋找路徑中其實(shí)已經(jīng)限制了最多經(jīng)過的點(diǎn)數(shù)，走到第N個(gè)點(diǎn)（即編號為N-1的點(diǎn)），便不再繼續(xù)走，或者沒有走到第N個(gè)點(diǎn)，而是已經(jīng)走到了終點(diǎn)即e，也不再繼續(xù)走，這樣已經(jīng)保證了每條路走過的點(diǎn)數(shù)都限制在N個(gè)以內(nèi)。（2）經(jīng)過N7和N12每條路走完之后，遍歷一下所有的點(diǎn)，看看其中是否有7和12這兩個(gè)值，沒有的話此路不滿足約束條件，否則繼續(xù)檢驗(yàn)其他條件。（3）經(jīng)過兩條綠的路線首先可以確定2、4、13、14必須通過，就是必須有這兩個(gè)數(shù)值，其次，2和4,13和14還必須相鄰出現(xiàn)，才能說明通過綠的路段。（4）不經(jīng)過紅的的路線，兩種解決方案第一：直接切斷N

14、11和N12間的路線，在表2中編號為11的節(jié)點(diǎn)中不添加12這個(gè)相鄰節(jié)點(diǎn)，在編號為12的節(jié)點(diǎn)中不添加11這個(gè)相鄰節(jié)點(diǎn)，這樣所得到的路線絕對不會(huì)經(jīng)過紅色路段。第二：每條路走完之后，遍歷一下所有的點(diǎn)，尋找N12與N13是否相鄰出現(xiàn)過，若出現(xiàn)過，這說明經(jīng)過了紅色路段，否則，未經(jīng)過，符合約束條件，繼續(xù)檢驗(yàn)其他條件。注：本算法用第一種解決方案實(shí)現(xiàn)！4.2.3 費(fèi)用分析經(jīng)過上述分析與計(jì)算，已經(jīng)求得了滿足所有約束條件并且經(jīng)過的點(diǎn)盡量少的路徑，接下來還需要考慮每條路徑的費(fèi)用。（1）費(fèi)用計(jì)算設(shè)有一條符合條件的路徑如下x0x1x2x3xN-2xN-1式（3）其費(fèi)用Fi = fx0x1+ fx1x2+ fx2x3+

15、fxN-3xN-2+fxN-2xN-1式（4）（2）費(fèi)用排序?qū)⑺玫降穆窂桨凑沼?jì)算的費(fèi)用升序排序，每條路的費(fèi)用將會(huì)一目了然，結(jié)合通過的點(diǎn)數(shù)、費(fèi)用選取最優(yōu)路徑。點(diǎn)編號01234567891011121314151617003110000010000000013010100000000000002110121000000000000310100221000000000040121010001000000005001200100310300000600020101200024300070001001010000000008000000210000001300904001300001100000010

16、00000100010120000011000000000110100010120000032000210200101300000040000020122114000000301000010100150000000030000210041600000000000111200117000000000000010410表3 費(fèi)用表4.2.3 算法設(shè)計(jì)核心代碼如下：void findMoreShortPath(int index, int *pointCount)int i;/將第一個(gè)點(diǎn)編號寫入路徑信息實(shí)例 *(allPathpathNum.pathPoint + (*pointCount)-1)

17、= index;/如果已經(jīng)到最后一個(gè)點(diǎn)或者走過的點(diǎn)數(shù)超過POINT_COUNT_MAX，對此路徑進(jìn)行處理 if(*pointCount = POINT_COUNT_MAX | index = END_INDEX)/如果此時(shí)最后一個(gè)點(diǎn)的編號為最后一個(gè)點(diǎn)的，那么繼續(xù)對此路徑進(jìn)行處理 if(index = END_INDEX)/判斷此路徑是否滿足約束條件，是則繼續(xù) if(checkPointOfPath()/給pathNum先加一，以防止覆蓋上一條符合條件的路徑 pathNum+;/因?yàn)椴粫?huì)再從頭開始遍歷，下一條路的前半部分與上一條路是相同的/因此將上一條路徑的信息賦給下一條路徑，分叉之后的路徑會(huì)在

18、上邊被修改 for(i = 0; i POINT_COUNT_MAX; i+)*(allPathpathNum.pathPoint + i) = *(allPathpathNum-1.pathPoint + i);else/如果不滿足以上條件，繼續(xù)向前走 for(i = 0; i 2-4-5-12-6-7-8-14-13-e式（5）s-2-4-5-12-6-7-6-14-13-e式（6）2、費(fèi)用最少的路徑有兩條，第一條經(jīng)過12個(gè)點(diǎn)，第二條經(jīng)過13個(gè)點(diǎn)，費(fèi)用都為13，路徑如下：s-2-4-5-6-7-8-14-13-12-16-e式（7）s-2-5-4-2-3-7-8-14-13-12-16-e

19、式（8）4.3對模型的檢驗(yàn)1.將N置為9或10時(shí)，程序運(yùn)行結(jié)果如下：圖3當(dāng)設(shè)置N為9或10時(shí)均未找到符合條件的路徑，說明經(jīng)過最少點(diǎn)數(shù)為9或10時(shí)均無法完成此任務(wù)，而設(shè)置為11及以更多時(shí)，會(huì)找到符合條件的路徑。這些檢驗(yàn)結(jié)果驗(yàn)證了3.3可行性分析的正確性，按照原題約束條件，此題無解。2. 將N置為11時(shí)，程序運(yùn)行結(jié)果如下：圖4所以得出節(jié)點(diǎn)最少的路徑有兩條，費(fèi)用分別為14和16：分別是s-2-4-5-12-6-7-8-14-13-e式（9）s-2-4-5-12-6-7-6-14-13-e式（10）3. 將N置為12時(shí)，程序運(yùn)行結(jié)果如下：圖5共找到73條符合條件的路徑，其中經(jīng)過11個(gè)點(diǎn)的路徑已被標(biāo)出，

20、費(fèi)用最少的情況為經(jīng)過12個(gè)點(diǎn)，費(fèi)用為13，可行路徑有一條，為：s-2-4-5-6-7-8-14-13-12-16-e式（11）4. 將N置為13時(shí)，程序運(yùn)行結(jié)果如下：圖6共找到1018條符合條件的路徑，從結(jié)果可以看到，也能找到一條費(fèi)用最少的路徑，為13，路徑如下：s-2-5-4-2-3-7-8-14-13-12-16-e式（12）4. 將N置為14時(shí)，程序運(yùn)行結(jié)果如下：圖7由此運(yùn)行結(jié)果分析可知，經(jīng)過14個(gè)點(diǎn)以及14個(gè)點(diǎn)以上，不會(huì)再有費(fèi)用最少的路徑。五、模型評價(jià)5.1模型優(yōu)缺點(diǎn)5.1.1模型優(yōu)點(diǎn) （1）算法中使用遞歸進(jìn)行路徑的檢索，這樣可以大大地提高代碼的運(yùn)行速度，即使數(shù)據(jù)比較龐大，也能很快求解

21、；（2）此模型看似是針對無向圖求解最優(yōu)路徑的模型，實(shí)際上針對有向圖同樣適用，并且計(jì)算起來更加快速，如何推廣位有向圖最優(yōu)路徑的模型在5.2模型改進(jìn)中講到；（3）對此網(wǎng)絡(luò)的規(guī)模增大縮小都是適用的，只需要對矩陣進(jìn)行擴(kuò)充，填入新增加的數(shù)據(jù)，修改少量參數(shù)；（4）能夠列出除最優(yōu)路徑之外的其他很多路徑，這為尋找其他合適的路徑提供了方便。5.1.2模型缺點(diǎn)（1）暫時(shí)所有的數(shù)據(jù)都是直接從源代碼中陸入進(jìn)去的，這就需要使用此模型的人非常熟悉這個(gè)模型才能保證修改后的矩陣和常量不出問題；（2）算法中，對約束條件進(jìn)過兩條綠線的判斷比較繁瑣，修改時(shí)容易出錯(cuò)；（3）模型中加入的影響因比素較少，在投放到實(shí)際問題中可能會(huì)出比較大

22、的偏差。5.2 模型改進(jìn)此模型此次計(jì)算是針對題目中的無向圖來設(shè)計(jì)與填充數(shù)據(jù)的，但是只要稍加改動(dòng)，便可以成為幾個(gè)無向圖最優(yōu)路徑算法。以本題目為例，假如只能從N2走到N4，那么要修改的只有兩個(gè)地方，而且是點(diǎn)的信息矩陣，將N4相鄰點(diǎn)的個(gè)數(shù)減1，相鄰點(diǎn)中將2除去，這樣便實(shí)現(xiàn)的從N2到N4的單方向，其他節(jié)點(diǎn)也是相同。完成了對無向圖的模型。參考文獻(xiàn)1 姜啟源. 數(shù)學(xué)模型.高等教育出版社. 2011.2 Thmoas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein著，殷建平，徐云，王剛，劉曉光，蘇朋，鄒恒明，王宏志 譯. 算法導(dǎo)論. 機(jī)

23、械工業(yè)出版社，2013.01. 附錄：源代碼如下：#include/最大允許通過的點(diǎn)數(shù) #define POINT_COUNT_MAX14/最后一個(gè)點(diǎn)的下標(biāo) #define END_INDEX17#define Booleanint #define TRUE1#define FALSE0/節(jié)點(diǎn)結(jié)構(gòu)體，包含相鄰點(diǎn)的個(gè)數(shù)adjoinPointCount，以及對應(yīng)的各個(gè)相鄰點(diǎn)adjoinPointtypedef struct POINTint adjoinPointCount;int adjoinPoint20;POINT;/路徑結(jié)構(gòu)體，pathPoint用來保存符合條件的路徑，以及費(fèi)用allFar

24、e typedef struct PATHint pathPointPOINT_COUNT_MAX;int allFare;PATH;/在遍歷路徑時(shí)，符合條件的路徑編號 int pathNum = 0;/保存所有的符合條件的路徑信息 PATH allPath;/點(diǎn)信息矩陣 POINT const point18 = /*0*/3,1,2,3,/*1*/3,2,4,9,/*2*/4,1,3,4,5,/*3*/4,2,5,6,7,/*4*/4,1,2,5,9,/*5*/7,2,3,4,6,9,10,12,/*6*/7,3,5,7,8,12,13,14,/*7*/3,3,6,8,/*8*/4,6,7

25、,14,15,/*9*/5,1,4,5,10,11,/*10*/4,5,9,11,12,/*11*/3,9,10,16,/*12*/5,5,6,10,13,16,/*13*/6,6,12,14,15,16,END_INDEX,/*14*/4,6,8,13,15,/*15*/4,8,13,14,END_INDEX,/*16*/4,11,12,13,END_INDEX,/*17*/0,0;/費(fèi)用矩陣 int const pathFare1818 = /* 01234567891011121314151617*/*0*/0,3,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,/*1*

26、/3,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,/*2*/1,1,0,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,/*3*/1,0,1,0,0,2,2,1,0,0,0,0,0,0,0,0,0,0,/*4*/0,1,2,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,/*5*/0,0,1,2,0,0,1,0,0,3,1,0,3,0,0,0,0,0,/*6*/0,0,0,2,0,1,0,1,2,0,0,0,2,4,3,0,0,0,/*7*/0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,/*8*/0,0,0,0,0,0,

27、2,1,0,0,0,0,0,0,1,3,0,0,/*9*/0,4,0,0,1,3,0,0,0,0,1,1,0,0,0,0,0,0,/*10*/0,0,0,0,0,1,0,0,0,1,0,1,2,0,0,0,0,0,/*11*/0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,/*12*/0,0,0,0,0,3,2,0,0,0,2,0,0,2,0,0,1,0,/*13*/0,0,0,0,0,0,4,0,0,0,0,0,2,0,1,2,2,1,/*14*/0,0,0,0,0,0,3,0,1,0,0,0,0,1,0,1,0,0,/*15*/0,0,0,0,0,0,0,0,3,0

28、,0,0,0,2,1,0,0,4,/*16*/0,0,0,0,0,0,0,0,0,0,0,1,1,2,0,0,0,1,/*17*/0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,4,1,0,;/查找符合條件的路徑 void findMoreShortPath(int index, int *pointCount);/檢查路徑是否符合條件 Boolean checkPointOfPath(void);/計(jì)算費(fèi)用 void caculateFare(void);/通過費(fèi)用排序 void sortPathByFare(void);/顯示路徑信息 void showPath(void);

29、void showPath(void)int i, j;if(pathNum != 0)for(i = 0; i pathNum; i+)for(j = 0; j %2d, *(allPathi.pathPoint + j);printf(總費(fèi)用為：%dn, allPathi.allFare);elseprintf(未找到符合的路徑！n);void sortPathByFare(void)int i, j;PATH temp;for(i = 0; i pathNum; i+)for(j = i; j allPathj.allFare)temp = allPathi;allPathi = allPathj;allPathj = temp;void caculateFare(void)int i, j;for(i = 0; i pathNum; i+)for(j = 0; j POINT_COUNT_MAX-1; j+)/若