公交線路的最優(yōu)選擇模型作者：劉剴，張旭，劉鵬摘要本文討論了最優(yōu)公交線路選擇的模型及其算法，并根據(jù)不同需求討論和建立了三個模型，分別為時間最短模型、費用最少模型和搜索模型，通過Dijkstra算法和高效的搜索算法，利用C++編程分別求出最優(yōu)解和近似解，對3個問題給與了解答。模型一：討論了在只考慮公交線路情況下的時間最短線路。本模型利用虛擬點的思想，將題中所給的公交線路轉化為賦權的有向網(wǎng)絡圖，并通過虛擬點邊權的含義，正確而清晰的表達了換乘公交車所需的時間，從而求得理論上的最優(yōu)解。利用Dijkstra算法在C++編程環(huán)境中加以具體實踐，求得所有題中數(shù)據(jù)解，并利用標號法反向追蹤列出具體路徑，依次求得題中點對最優(yōu)值為：S3359分S1828:64分鐘；S1557分S0481:99分鐘；S0971分S0485:103分鐘；S0008分S0073:59分鐘；S0148分S0485:102分鐘；S0087分S3676:46分鐘；模型二：討論了在只考慮公交情況下的時間最短線路。本模型利用構造完全圖將所給的公交線化為一道可以用Dijkstra算法求解的最短路問題。通過C++編程的實現(xiàn)，求得各最優(yōu)解。依次求得題中點對最低費用為S3359分S1828:3元； S1557分S0481:3元；S0971分S0485:3元；S0008分S0073:2元； S0148分S0485:3元； S0087分S3676:2元；模型三：討論了基于實際情況的一種高效簡單的算法。其核心思想是起始點和終點點同時進行對公交線路進行搜索。此模型雖不能每次求得最優(yōu)理論解，但時間復雜度低，能快速處理本題中的大量數(shù)據(jù)并出解。本論文還通過比較大量數(shù)據(jù)點的最優(yōu)解和近似解的分析與比較，考察差距比參數(shù)a的大小和穩(wěn)定范圍，驗證模型三不失為一個可行的模型和算法。如求得S0941-S0485在問題一中的最優(yōu)解為103分鐘，在問題二中為96,僅與最優(yōu)解95差1分鐘。依次求得題中點對最低費用為S3359分S1828:64分鐘；S1557分S0481:106分鐘； S0971分S0485:103分鐘；S0008分S0073:83分鐘；S0148分S0485:106分鐘； S0087分S3676:46分鐘；推廣的模型一：在建立模型一之后，對于問題二僅僅需要增添有向邊，即可解決。依次求得題中點對最低費用為S3359分S1828:61.5分鐘；S1557分S0481:99分鐘； S0971分S0485:95分鐘；S0008分S0073:53.5分鐘；S0148分S0485:86.5分鐘；S0087分S3676:36分鐘；由于本題是一個數(shù)據(jù)量相當大的問題，因此算法的可行性變得及其重要。我們從復雜度的角度分析以上模型，證明其可行性，尤其模型三的復雜度最低，也表明了其算法的有效性。關鍵詞最后本文推廣了模型二，三，并考慮了定義時間費用權重系數(shù)的時間費用綜合最優(yōu)解求解的模型。關鍵詞Dijkstra算法，網(wǎng)絡圖，Kn完全圖，搜索算法，算法復雜度，虛擬點一、問題重述國人翹首期盼的29屆奧運會明年8月將在北京舉行，屆時由于大量觀眾將會乘公交觀看奧運比賽，公交線路選擇問題成為人們討論的熱點問題。如何從實際出發(fā)，設計一個解決公交線路選擇問題的自主查詢系統(tǒng)以滿足不同需求，成為我們亟待解決的問題。這里面的核心是查詢系統(tǒng)中線路選擇模型的建立和算法的編制。1、 考慮公汽線路，給出兩公汽之間線路選擇問題的一般數(shù)學模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始點到終點站之間的最佳路線（要有清晰的評價說明）。2、 設同時考慮公汽與地鐵線路，解決以上問題。3、 設又知道所有站點之間的步行時間，請你給出任意兩點時間線路選擇問題的數(shù)學模型。、問題的符號說明與假設1、問題符號說明NL：表示公交線路總條數(shù)。Li：表示第i條公交線路；Si：表示公交車站；Di：表示地鐵站；stop_number[i]：表示第i條公交路線上的總站點數(shù)；stop[i][j]：表示第i條公交線路上的第j個站點；set[i]:表示一個集合，是第i條公交線路上站點的集合;w(i,j):表示邊e（i,j）的權值；S：表示起始站；D：表示終點站；LS：表示經過起始站S的公交路線集合；LS[i]：表示經過起始站S的第i條公交線路；LD：表示經過終點站D的公交路線集合；LD[j]：表示經過終點站D的第j條公交線路；p：表示經過起始站S的公交線路總條數(shù)；q：表示經過終點站D的公交線路總條數(shù)；stopLS[i][u]：表示經過起始站S的第i條公路上的第u個站；stopLD[j][v]：表示經過起始站D的第j條公路上的第v個站；numberLS[i]:表示經過起始站S的第i條公交線上總站點數(shù)；numberLD[j]:表示經過起始站D的第j條公交線上總站點數(shù)；w’(D.,S.)表示有向邊e（D.,S.）的權值；WK(u,v):表示u,v之間步行時間；2、問題的假設（1） 、地鐵轉公交不考慮費用；（2） 、對于環(huán)形的理解，環(huán)形有單環(huán)形和雙環(huán)形之分，這里我們考慮雙向的環(huán)形；（3） 、不考慮地鐵、公交車的運行時間；(4)、對環(huán)形地鐵如假設2,也設為雙向環(huán)形。三、問題分析與模型的建立公交線路選擇應能幫助查詢者快速地選擇出行路徑、換乘路線等，既提升了出行者的效率，又優(yōu)化了公交資源的配置，提高了交通運輸?shù)男屎统鞘械男畔⒎栈?。基于此我們考慮不同需求，從實際出發(fā)設計最優(yōu)路線。從全局出發(fā)我們分析此題是個典型的網(wǎng)絡題，因此我們需要從合理構造網(wǎng)絡，明確表示邊權、節(jié)點的實際意義角度，利用最短路算法的思想予以建模。這題中算法的編制我們以經典的最短路算法Dijkstra算法為基礎進行衍生與變形，從而得到符合我們需要的算法。由于本題有三個小題我們著手逐個分析，依次建立模型。1、首先我們對問題一進行分析在僅考慮公交路線的情況下，我們考慮以下兩種需求：一是不考慮費用的時間最短路；二是不考慮時間的費用最短。1.1、模型一：只考慮公交系統(tǒng)下的時間最短模型第一種需求我們想得到關于時間最短的最短路模型最短。我們以節(jié)點表示公交線路上的各站點，邊權表示相鄰站點的平均行駛時間(包括停站時間)即3分鐘。第一種需求的難點在于如何在建立的網(wǎng)絡圖上表達“公汽換乘公汽平均耗時”，本模型中我們引建立基于“公交線路”的網(wǎng)絡圖，并利用Dijkstra算法予以求解。在建立模型一的過程中，由于題中原始數(shù)據(jù)量很大，我們構造一個事例來幫助闡述整個建網(wǎng)絡圖的過程。設有三條線路L］：1-2-3-4-5；L2：1-6-7；L5：6-5。我們考慮從1到5的時間最短路。、每一條線路看成一個分支，“平行”地放置，構成一個有NL個連通分支的圖。每一條邊上定義權為3，表示相鄰站點的平均行駛時間。本實例為：圖1、找出各條線路之間具有的相同節(jié)點(如L1和L2都含有站點1)，用“一”連接之，并在相同節(jié)點之間賦權值為5,表示公汽換乘公汽平均耗時。

本實例中L1和L2中都含有站點1,L2和L3中都含有站點6,連接1—1,6—6,為后文闡述方便，另一個1記為1’，5記為5’形成如下網(wǎng)絡圖：另一實例若有L］：1—2—3—4—5；L2：1—2—7；L3：6—2—9則建立網(wǎng)絡圖應為:（3）、建立了圖2網(wǎng)絡后，圖上任意一條路對應于與一個路線選擇方案，這樣便可以利用Dijkstra算法算出從不同出發(fā)點到終點站的最短路，取最小值便得到從起始點到終點的嚴格意義上的時間最短路。在本實例中算出從1到5,1到5’，1’^05,1’到5’的最短路，即可得到最短時間為11；其路線為乘L2從1’到6再轉L3從6到5’，總時間為3+5+3=11。將以上方法應用于第1小題中，得到如下結果：起始站點具體路徑耗時/min起點站車站點車站點車站點車站點車站點S3359——S1828S3359L484S3727L485S1784L167182864S1157——S0481S1557L084S1919L189S3186L091S0903L239S048199S0971——S0485S0971L013S2519L290S2159L469S0485103S0008——S0073S0008L198S3766L476S2085L017S0604L328S0525L103S007359S0148——S0485S0148L308S3604L081S2361L156S3351L417S0485102S0087——S3676S0087L021S0088L231S0427L097S367646程序見附錄1.2、模型二：只考慮公交系統(tǒng)選擇費用最短對第二種需求，我們想得到關于費用最短的最短路模型。由于公汽票價分為單一票價與分段票價兩種。故其中的難點是如何在圖中清晰的表達“分段計價”的費用?？紤]到公交路線由于費用分段計價很難在模型一的圖中明確地表示，因此我們將建立一個基于“地圖模式”的最短路網(wǎng)絡再通過Dijkstra算法求出費用最短的最優(yōu)解。同樣的，在建圖過程中我們以實例闡明構建思想。實例：設有如下公交路線L]：1—2—3—4；L2：1—4—7。0--2站：1兀；2站以上：1.5元。模型二的網(wǎng)絡圖構建如下：設共有NL條公交線路，第i條公交線路有stop_number[i]個站點。其具體站點表示為stop[i][1],stop[i][2]，…，stop[i][j]…，stop[i][stop_number[i]]；設置計數(shù)器i=1;網(wǎng)絡圖初始G(V，E)為空；、若i>NL，圖構造結束；否則，對公交線匕路上所有的站點建立一個K…血[明間完全圖。權值w(m,n)其中m，ngset[i]，表示第i條線從m到n的費用，利用分段計價算出，或根據(jù)有些站點是單一價算出，其中m，ngset[i]；、將產生的K圖網(wǎng)絡中加入到G(V,E)中去；具體如下：若K圖中邊e(u,v)wG，u，vgk；則在圖G中增加u，v節(jié)點(若有則不需增加)，邊權值為w(u,v)；若K圖中邊e(u,v)gG，u，vgk；則在G圖中該邊權值取min(該邊在K圖中的權值w(u,v)，該邊在圖G中的權值w’(u,v)｝；對所有K圖中的邊e(u,v)均進行如此操作；、i=i+1；、重復第(1)步。類似地我們也采用實例進行說明：

i=1（第一條公交線路）（1）、建立第一條公交線路1—2—3—4的K4圖為:此時G圖為空，加入K4圖后G圖即為上圖；i=2（第二條公交線路）（2）、建立第二條公交線路1—4—7的K3圖為:K3圖將上圖加入G圖，合并時會產生w’（1,4）=1<w（1,4）=1.5,其中e’（1,4）gK，e（1，4）gG，因此G圖中的邊w（1,4）的權值改為1，合并后的圖為：

建立完圖形之后，即利用Dijkstra算法可以算出任意兩點間的最短距離。對于題中給出的6對頂點，我們用如上算法算出最優(yōu)解為：起始站點費用/元具體路徑站點車站點車站點車站點S3359一一S18283S3359L436S1784L217S1828L436S1241L167S1157—一S04813S1557L363S1919L189S3186L460S0481L084L417S3919L166S0971—一S04853S0971L103S2184L417S0485L119S0354L377S0008一一S00732S0008L159S0400L474S0073L463S2083L057S0148一一S04853S0148L308S0036L155S3332S2210L417S0485S0087一一S36762S0087L454S3496L209S3676S1893備注：實際最低費用路線不止表中所列，此處僅列舉幾條，詳細數(shù)據(jù)請見電子版附錄文件夾。1.3、模型三：只考慮公交系統(tǒng)情況下的基于實際情形的路徑搜索算法在實際情況中，如本題對應于北京城發(fā)達公交線路，那么我們可以想象從一個站點到另一個站點的轉車次數(shù)是比較少的。在本模型中，我們考慮了一個基于實際的更快捷明了的算法來找出兩站點之間的最短路，并和模型一中算出的最優(yōu)解進行比較。模型分析如下：我們考慮轉車次數(shù)^2的從起始站S到目標站D的搜索算法。

我們采用LSI,LS2?LSp表示經過S站的公交線路；LD1,LD2?LDp表示經過D站的公交線路。、不轉車情況枚舉LS集合中LSi(1忍i忍q)和LD集合中LDj(l^j^q)若LSi=LDj,則表明S-D中有直達車LSi(或LDj)這樣對于一條路徑在計算機中利用二重循環(huán)即可。示意圖如下：、轉車一次情況枚舉LS集合中LSi(1忍i忍q)和LDj(l^j^q)；對LSi和LDj依次枚舉LSi中的每一個站stopLS[i][u](1^u^numberLS[i])和LDj中的每一個站點stopLD[j][v](1WvWnumberLD[j])其中numberLS[i]表示第LS[i]條線路經過的站點數(shù)；numberLD[j]表示LD[j]經過的總站點數(shù)；若stopLS[i][u]=stopLD[j][v]表明LSi和LDj在stopLS[i][u]相交這樣就在S和D中又找出一條路徑；重復第一步直至所有線路枚舉完畢。示意圖如下：、轉車二次情況[1]枚舉LS集合中LSi(1WiWq)和LDj(1WjWq)；

[2]對LSi和LDj依次枚舉LSi中的每一個站點stopLS[i][u]（1忍u忍numberLS[i]）,LDj中的每一個站點stopLD[j][v]（1^v^numberLD[j]）（以上兩步與轉車一次前兩步相同）；在stopLS[i][u]乏stopLD[j][v]的前提下，我們檢查這兩個站點是否在另一條公交線路中。若有就找到這樣一條轉乘兩次可以從S到達D的路徑；[4]重復[1][2]兩步，直至所有線路與線路上的點數(shù)枚舉完畢。示意圖如下：建立此模型后，我們用C++編程實現(xiàn)上述算法，并通過dijkstra最短路算法求得以下結果。(1)、S3359一一S1828車站點車站點車耗時/minL484S3727L485S1784L217或L16764S3697S2027S1746L474S2903L469S2027L436S2903L365L352L324S1746S2027L132S2903L122L015

(2)、S1557—S0481車站點車站點車耗時/minL363S1919L189S3186L460106L084(3)、S0971—S0485車站點車站點車耗時/minL013S2517L291S2159L469103S2480(4)、S0008—S0073車站點車耗時/minL159（下行）S2683L058（下行）83S029183S361483S049183S255983S331583S2559L459（上行）83S0400L474（上行）83S263383S305383L463（下行）S2083L057（上行）83(5)、S0148—S0485車站點車站點車耗時/minL308S0036L155S3351L417106S3332S2210(6)、S0087—S3676車站點車站點車耗時/minL021S0088L231S0427L09746L4622、對問題二進行分析同時考慮公汽與地鐵線路，我們設計的最優(yōu)路線還是考慮以上兩種需求：一是不考慮費用的時間最短；二是不考慮時間的費用最短。2.1、模型一：同時考慮公汽與地鐵線路選擇時間最短由于問題2是在問題1的情況下加入地鐵，所以問題2的模型一是問題1的模型一的推廣（為表述簡便我們把問題2的模型一記作問題1的模型一的新模型一下面模型二同理記作新模型二）模型構建如下：將地鐵看成另一條“公交線”，同樣可以在圖上新建界點來表示地鐵站，而地鐵上任意點相連，表示地鐵可以互通，其中權值賦為地鐵站相互到達時間二地鐵一站運行時間*相隔站數(shù)；（如d地鐵上1號站點和4號站點相連，表示1，4站點可相互到達；其權值為地鐵運行時間*相隔站數(shù)二2。5*3=7。5）；同理，若地鐵站Di和公交站Si相同，則在圖上連接Di和Si，令權值w’（Di，Si）=7；表示地鐵轉公交需要7分鐘；令權值w’（Si，Di）=6，表示公汽轉地鐵的時間為6；實例如下：我們在圖的情況下，加入地鐵線T1，則加入后的網(wǎng)絡圖為：建立以上網(wǎng)絡圖后，便可通過Dijkstra算法算出任意兩點的時間最短路。對題中所列6對起始點我們通過上述模型和算法求得最優(yōu)解為：

起始站點八、、具體路徑（其中：一表示步行轉車）耗時/min起點站車站點車站點車站點車站點S3359——S1828S3359L324S2027L201S0609一D12T1D21-S0464L269S182861.5S1157——S0481S1557L084S1919L189S3186L091S0903L239S048199S0971——S0485S0971L094S0567一D01T1D15—S2534L156S3351L417S0488595S0008——S0073S0008L200S2534一D15T1D12T2D25—S0525L103S007353.5S0148——S0485S0148L024S1487一D02T1D15—S2534L156S3351L417S048586.5S0087——S3676S0087L021S0630一D29T2D36—S3676362.2、模型二；同時考慮公汽與地鐵線路選擇費用最短與問題2的模型一類似，模型二看成是問題1的模型二的推廣。建模思想如下：將地鐵當成另一條“公交線”，建立此條“公交線”的K完全圖，因為地鐵線統(tǒng)一標價3元，因此此K圖所有邊權值為3,再“加入”到原模型二的圖中。由于地鐵和公交站點之間轉換不需要費用，因此只需根據(jù)地鐵站與公交站相連信息將對應點相連，其權值賦為0（表示轉換不需費用）。我們用實例闡明若加入地鐵3-2-7則形成下圖：

形成后我們采用原模型二的Dijkstra最短路算法即得結果如下:起始站點費用/元具體路徑站點車站點車站點車站點S3359一一S18283S3359L436S1784L217S1828L436S1241L167S1157—一S04813S1557L363S1919L189S3186L460S0481L084L417S3919L166S0971—一S04853S0971L103S2184L417S0485L119S0354L377S0008一一S00732S0008L159S0400L474S0073L463S2083L057S0148一一S04853S0148L308S0036L155S3332S2210L417S0485S0087一一S36762S0087L454S3496L209S3676S18932.3、模型三：同時考慮公汽與地鐵線路的分枝搜索算法與問題2的模型二類似，模型三看成是問題1的模型三的推廣。具體建模如下：將地鐵當成另一條“公交線”，如果最短路線經過一條地鐵，那么必然要經過兩次轉車，（進出地鐵各一次），那么將模型三中提到的“另一條公路”即為推廣模型中的地鐵。用類似的轉兩次車算法便可算出所有經過一條地鐵的路徑。示意圖如下：

建立此模型后，我們用C++語言實現(xiàn)上述算法，得到如下結果:起始站點具體路徑（其中：一表示步行換乘）耗時/min起點站車站點車站點車站點S3359一一S1828S3359L474S0856-D28T2D38-S3262L041S1828117S1557一一S0481S1557L084S1919-D20T1D13-S2633L447S0481120。5L084S0978-D32T2D24-S0537L516S0971—一S0485S0971L094S0567-D01T1D21-S0464L395S048596L119S0567-D01T1D21-S0466L450S0008一一S0073S0008L159S0630-D29T2D25—S0525L103S007355L259S3874-D30T2D25—S0525L103S0148一一S0485S0148L024S1487-D02T1D21—S0464L469S048587L104S0087一一S3676S0087L021S1427-D30T2D36S367636S0630-D29T2L028S0608-D12T2D36一S0427L097程序見附錄二1、問題三的分析；對于問題三，加入步行后，我們便不再考慮單獨費用最短的模型，因為既然告訴你所有點的步行時間，那么任意點之間只需要步行即可，費用為零。因此我們考慮時間最短的情況，這里我們利用本論文中的推廣模型算法來分析這一問題。從某種意義上講，步行也可以理解為一個“交通工具”，那么在原網(wǎng)絡上可以設想通過添加或改變權值來解決。具體模型：在推廣的模型一的網(wǎng)絡圖G(V,1)中對任意的u,vEG(V,1)，如果他們之間不存在邊，那么連接u,v邊，令w(u,v)=WK(u,v)；若u,v之間存在邊，那么令w(u,v)=min(w(u,v),WK(u,v)+c}；c為常數(shù)，表示等待公交車的時間。四、復雜度分析考慮到本題社及大批量數(shù)據(jù)處理，又要通過C++編成加以實現(xiàn)，那么進行算法復雜度的分析就顯得很有意義，否則很可能一個不錯的模型和算法會由于復雜度太高而無法實現(xiàn)。本論文下面將從復雜度角度闡述以上3個模型的可行性。定理1：Dijkstra算法復雜度只與圖中點數(shù)N有關且為O(N)，與邊數(shù)無關。問題一的算法復雜性分析模型一：在該模型中，我們考慮所建圖的點數(shù)(公交線數(shù)X平均每條線的站點數(shù))。.??所建圖的點數(shù)^520X40=20800「?算法復雜度O(N2)=208002=4.3X108現(xiàn)在計算機的平均運行速度為：108次/S，所以此算法完全可行。模型二我們對模型二采取與模型一類似的分析方法，模型二是基于“地圖式”的網(wǎng)絡，站點數(shù)^4000，「?算法復雜度O(N2)=40002=1.6X107故此算法也是可行的。模型三：在模型三中，我們分類討論轉車次數(shù)：一是不轉車(即轉車次數(shù)為0)，二是轉車次數(shù)不為0(^2)。1、 不轉車在該條件下，算法思想主要涉及一個兩重循環(huán)，分別枚舉經過起始站點的公交線路；算法復雜度為經過起始點的公交路線的平方級別，約為102(很小)。2、 轉一次或兩次車在該條件下，算法思想主要涉及一個四重循環(huán)，分別枚舉經過起始站點的公交線路和相應公交線路上的站點，由于經過某個點的公交路線不大于20路，一條公交上站點不大于100，則復雜度不大于20X20X40X40=6.4X105,完全可行。三個模型運算速度，結果分析與比較模型一用于求解時間最短路，本模型在建立的過程中其實應用了“虛擬點”的思想。事實上這是個在計算機網(wǎng)絡流編程一個重要的思想，應用于本模型可以嚴格的證明求出的是最優(yōu)解。模型二用于求解路費最短路，從理論上講是一個正確的算法。但事實上，在本題實際情況中，轉三次及其以上最低就需要4元，而對于題中所給點我們完全能通過模型三的算法求出只需要轉一次，轉兩次中小于4元的路徑，而且相當多。在加入地鐵后，由于地鐵就要三元，且還需要轉公交，費用最少在5元以上，因此用模型二求出的最優(yōu)解必然在模型三求出的解中。對于模型三，其算法復雜度低，運行時間最快，所以在這部分的分析中，我們著重研究模型一和模型二求出的解之間的差別，現(xiàn)附表如下：模型一與模型三結果比較與分析起始站點問題一問題二模型一模型三a模型一模型三aS3359—5644%S1557—S0481991067%99120.522%S0971—S0485103103095961%S0008fS0073598341%53.5553%S0148—S04851021064%86.5871%S0087—S36764646036360其中，定義“差距比例系數(shù)”a=(最優(yōu)解-近似解)/最優(yōu)解為X100%。從表中我們可以看出不管是問題一還是問題二，大部分都比較小，說明從整體上看模型三有比較好的擬合最優(yōu)解，但個別點對也存在值比較大的現(xiàn)象，這也是模型三的一個缺點所在，有待進一步改進模型三的算法，或考慮轉車次數(shù)更高時的算法。模型的推廣；模型一和模型二分別考慮了單獨時間最短和單獨費用最低的模型，此外，我們可以用過定義權重系數(shù)來綜合考慮時間和費用的最優(yōu)路，基本模型思想如下：構造網(wǎng)絡G(V,E),v表式北京各個站點，定義邊權值w(u,v)=pTuv+(1-p)Cuv其中，P:表示時間權重系數(shù)，Tuv:表示從u到v的最短路徑，Cuv:表示從u到v的最短時間。那么尋找最優(yōu)解，就是在此網(wǎng)絡圖上用Dijkstra算法求出最短路。參考文獻：戴一奇，胡冠章，陳衛(wèi)，圖論與代數(shù)結構，北京：清華大學出版社,1995徐立華，求解最短路問題的一種計算機算法.系統(tǒng)工程，1989李元臣，劉維群，基于Dijkstra算法的網(wǎng)絡最短路徑分析.微計算機應用，2004柴登峰，張登榮.前N條最短路徑問題的算法及應用[M].浙江大學學報(工學版)，2002，36(5)：531—534徐全智，楊晉浩，數(shù)學建模，北京：高等教育出版社，2003Thomas,H.Cormen,IntroductiontoAlgorithms,TheMITPress,2003陳簫楓，蔡秀云，唐德強.最短路徑算法分析及其在公交查詢的應用[J].工程圖學學報。2001(3)：2O一24劉光明，蔡先華，苗聰.一種城市公交查詢的算法及其應用[J]交通運輸工程與信息學報，2005，3(2)：87—91附錄一#include<stdio.h>#include<vector>#include<string>#include<iostream>usingnamespacestd;constdoubleMax=99999999;doubleBS2BS=100;//Bus一站時間doubleTS2TS=2.5;//Train一站時間doubleB2B=100;//Bus轉車doubleT2T=80;//Train轉車doubleT2B=14;//Train轉BusdoubleB2T=12;//Bus轉TrainconstintNB=5000;vector<int>BusStop[5000];constintNT=100;vector<int>TrainStop[100];structedge{intstop;doubledis;stringway;edge(intstop,doubledis,stringway){this->stop=stop;this->dis=dis;this->way=way;}};stringStopName[50000];vector<edge>Map[50000]; 〃站點圖intN; 〃站點數(shù)目intpre[50000];doubledis[50000];boolmark[50000];voidInputBus(){chartmp[10000];cin.clear();freopen("Bus.txt”,"r",stdin);while(true){stringline;getline(cin,line);while(line=="")getline(cin,line);if(line=="END")break;stringway=line;getline(cin,line);getline(cin,line);if(line.substr(0,2)=="上"){line.erase(0,6);strcpy(tmp,line.c_str());char*p;p=strtok(tmp,"S-\n");intf=-1;while(p!=NULL){intsn=atoi(p);N++;StopName[N]=string("S")+string(p);BusStop[sn].push_back(N); //**iff!=-1){Map[f].push_back(edge(N,BS2BS,way));//**}f=N;p=strtok(NULL,"S-\n");}getline(cin,line);line.erase(0,6);strcpy(tmp,line.c_str());p=strtok(tmp,"S-\n");f=-1;while(p!=NULL){intsn=atoi(p);N++;StopName[N]=string("S")+string(p);BusStop[sn].push_back(N); //**iff!=-1){Map[f].push_back(edge(N,BS2BS,way));//**}f=N;p=strtok(NULL,"S-\n");}}elseif(line.substr(0,2)=="環(huán)"){line.erase(0,6);strcpy(tmp,line.c_str());char*p;p=strtok(tmp,"S-\n");intf=-1;intfirst=-1;while(p!=NULL){intsn=atoi(p);if(sn==first)break;N++;StopName[N]=string("S")+string(p);BusStop[sn].push_back(N); //**iff!=-1){Map[f].push_back(edge(N,BS2BS,way));//**Map[N].push_back(edge(f,BS2BS,way));}f=N;if(first==-1)first=f;p=strtok(NULL,"S-\n");}Map[f].push_back(edge(first,BS2BS,way));Map[first].push_back(edge(f,BS2BS,way));}else{strcpy(tmp,line.c_str());char*p;p=strtok(tmp,"S-\n");intf=-1;while(p!=NULL){intsn=atoi(p);N++;StopName[N]=string("S")+string(p);BusStop[sn].push_back(N); //**iff!=-1){Map[f].push_back(edge(N,BS2BS,way));//**

Map[N].push_back(edge(f,BS2BS,way));}f=N;p=strtok(NULL,"S-\n");}}}//endwhile}voidProcessSameBusStop(){inti;for(i=0;i<NB;i++){if(BusStop[i].empty())continue;vector<int>::iteratorj,k;for(j=BusStop[i].begin();j<BusStop[i].end();j++)for(k=j+1;k<BusStop[i].end();k++){Map[*j].push_back(edge(*k,B2B,"轉車")); //**Map[*k].push_back(edge(*j,B2B,"轉車")); //**}}}voidInputTrain(){chartmp[10000];cin.clear();freopen("Train.txt”,"r",stdin);while(true){stringline;getline(cin,line);while(line=="")getline(cin,line);if(line=="END")break;stringway=line;getline(cin,line);getline(cin,line);if(line.substr(0,2)=="環(huán)"){line.erase(0,6);strcpy(tmp,line.c_str());char*p;p=strtok(tmp,"D-\n");intf=-1;intfirst=-1;while(p!=NULL){intsn=atoi(p);if(sn==first)break;N++;StopName[N]=string("D")+string(p);TrainStop[sn].push_back(N); //**iff!=-1){Map[f].push_back(edge(N,TS2TS,way));//**

Map[N].push_back(edge(f,TS2TS,way));}f=N;if(first==-1)first=f;p=strtok(NULL,"D-\n");}Map[f].push_back(edge(first,TS2TS,way));Map[first].push_back(edge(f,TS2TS,way));}else{strcpy(tmp,line.c_str());char*p;p=strtok(tmp,"D-\n");intf=-1;while(p!=NULL){intsn=atoi(p);N++;StopName[N]=string("D")+string(p);TrainStop[sn].push_back(N); //**iff!=-1){Map[f].push_back(edge(N,TS2TS,way));//**Map[N].push_back(edge(f,TS2TS,way));}f=N;p=strtok(NULL,"D-\n");}}}//endwhile}voidProcessSameTrainStop(){inti;for(i=0;i<NT;i++){if(TrainStop[i].empty())continue;vector<int>::iteratorj,k;for(j=TrainStop[i].begin();j<TrainStop[i].end();j++)for(k=j+1;k<TrainStop[i].end();k++){Map[*j].push_back(edge(*k,T2T,"轉車")); //**Map[*k].push_back(edge(*j,T2T,"轉車")); //**}}}voidProcessTrainBusStop(){chartmp[10000];cin.clear();freopen("Train2-Bus.txt","r",stdin);while(true){stringline;inttid,bid;getline(cin,line);if(line=="")break;strcpy(tmp,line.substr(1,2).c_str());tid=atoi(tmp);line.erase(0,5);strcpy(tmp,line.c_str());char*p;p=strtok(tmp,"S,");while(p!=NULL){bid=atoi(p);vector<int>::iteratorj,k;for(j=TrainStop[tid].begin();j!=TrainStop[tid].end();j++)for(k=BusStop[bid].begin();k!=BusStop[bid].end();k++){Map[*j].push_back(edge(*k,T2B,"地鐵轉公交")); //**Map[*k].push_back(edge(*j,B2T,"公交轉地鐵")); //**}p=strtok(NULL,"S,");}}cin.clear();freopen("Train1-Bus.txt”,"r",stdin);while(true){stringline;inttid,bid;getline(cin,line);if(line=="")break;strcpy(tmp,line.substr(1,2).c_str());tid=atoi(tmp);line.erase(0,5);strcpy(tmp,line.c_str());char*p;p=strtok(tmp,"S,");while(p!=NULL){bid=atoi(p);vector<int>::iteratorj,k;for(j=TrainStop[tid].begin();j!=TrainStop[tid].end();j++)for(k=BusStop[bid].begin();k!=BusStop[bid].end();k++){Map[*j].push_back(edge(*k,T2B,"地鐵轉公交")); //**Map[*k].push_back(edge(*j,B2T,”公交轉地鐵")); //**}p=strtok(NULL,"S,");}}}voidDijkstra(intS){inti,j,k;for(i=0;i<N;i++){dis[i]=Max;pre[i]=-1;mark[i]=false;}vector<int>::iteratorp;for(p=BusStop[S].begin();p!=BusStop[S].end();p++){dis[*p]=0;pre[*p]=*p;}intct=0;while(true){//cerr<<ct++<<endl;doublemin=Max;k=-1;for(i=0;i<N;i++)if(!mark[i]&&dis[i]<min){min=dis[i];k=i;}if(min==Max)break;mark[k]=true;vector<edge>::iteratorq;for(q=Map[k].begin();q!=Map[k].end();q++)if(!mark[q->stop]&&dis[k]+q->dis<dis[q->stop]){dis[q->stop]=dis[k]+q->dis;pre[q->stop]=k;}}}voidProcessAns(intT){intk=-1;doublemin=Max;vector<int>::iteratorp;for(p=BusStop[T].begin();p!=BusStop[T].end();p++){if(dis[*p]<min){min=dis[*p];k=*p;}}if(min==Max){cout<<"Noway!"<<endl;return;}while(pre[k]!=k){intj=pre[k];stringname;vector<edge>::iteratorq;for(q=Map[j].begin();q!=Map[j].end();q++)if(q->stop==k)break;cout<<StopName[k]<<" "<<k<<" "<<q->way<<endl;k=pre[k];}cout<<min<<endl;intnum,i;intS[1000];intT[1000];intmain(){cin.clear();freopen("config.txt”,"r",stdin);cin>>BS2BS>>TS2TS>>B2B>>T2T>>T2B>>B2T;cin.clear();freopen("input.