廣東省中小城市公交線路評估

廣東省中小城市公交線路評估EvaluationoftransitroutesinsmallandmediumcityofGuangdong摘要本文以汕尾市城區(qū)的公交網(wǎng)絡(luò)作為研究對象，通過分析汕尾市城區(qū)的公交換乘情況，采集汕尾市城區(qū)的公交線路及其站點信息等，選擇使用java程序語言編程，運(yùn)用二維數(shù)組來完成以公交線路站點的信息存儲和以公交站點為結(jié)點的大矩陣的乘法算法；并運(yùn)用鄰接矩陣能用于求圖節(jié)點之間是否能相互連通的特點，通過求矩陣的平方來完成一次換乘的功能，通過求矩陣的立方完成二次換乘的功能。后期通過確定起點來遍歷站點數(shù)組尋找存在的一個或兩個中點能達(dá)到終點的遍歷方式，優(yōu)化了鄰接矩陣求平方，立方的方法來達(dá)到一次，二次換乘的目的。最后通過與各種常見的最短路徑算法之間的時間效率比較，來說明鄰接矩陣通過求超大矩陣的一次方和二次方來完成一次換乘和兩次換乘方案的高效性以及穩(wěn)定性。關(guān)鍵詞：公共交通；大矩陣乘法；鄰接矩陣；換乘AbstractThispapertakesthepublictransportationnetworkofShanweiCityastheresearchobject,throughanalyzingthepublictransportationtransfersituationofShanweiCity,collectingthepublictransportationlineandstationinformationofShanweiCity,choosingJavaprogramminglanguage,usingtwo-dimensionalarraytocompletetheinformationstorageofthepublictransportationlinestationandthemultiplicationalgorithmofthelargematrixwiththepublictransportationstationasthenode,andusingadjacencymatrixItcanbeusedtofindwhetherthegraphnodescanbeconnectedwitheachother.Itcancompletethefunctionofprimarytransferbyfindingthesquareofthematrix,andcompletethefunctionofsecondarytransferbyfindingthecubeofthematrix.Inthelaterstage,thestartingpointisdeterminedtotraversethearrayofstationstofindthetraversalmodewhereoneortwomidpointcanreachtheendpoint,andthemethodoffindingthesquareandcubeoftheadjacencymatrixisoptimizedtoachievethepurposeofprimaryandsecondarytransfer.Finally,bycomparingthetimeefficiencywithothercommonshortestpathalgorithms,itshowsthattheadjacencymatrixcanachievetheefficiencyandstabilityofonetransferandtwotransferschemesbyfindingthefirstandsecondpowerofthesuperlargematrix.Keywords:Publictransport;argematrixmultiplication;djacencymatrix;transfer

目錄第一章緒論 第一章緒論1.1課題目的與意義自從17世紀(jì)以來，隨著城市化的發(fā)展，伴隨而來的是公共交通出現(xiàn),一個城市的公交系統(tǒng)已然成為整個城市交通系統(tǒng)中最為重要的組成部分之一。[9]它的發(fā)展水平甚至是衡量一個城市現(xiàn)代化程度的重要標(biāo)志,越發(fā)達(dá)的公交系統(tǒng)意味著城市化的發(fā)展越現(xiàn)代化。同時一個城市的公交系統(tǒng)更是該城市的綜合經(jīng)濟(jì)實力、城市居民生活的水平的縮影之一。一個城市的公共交通系統(tǒng)是城市交通運(yùn)輸網(wǎng)的基石，是廣大群眾出行時選擇花費較為少且經(jīng)濟(jì)實惠的出行方案，是生活必不可少的社會公共設(shè)施，是一個城市的建設(shè)和城市發(fā)展的重要基礎(chǔ)之一；在中小城市，公交交通更加現(xiàn)得尤為重要！公共交通系統(tǒng)更是城市環(huán)境規(guī)劃和道路規(guī)劃的主要參考之一。作為城市交通的重要基礎(chǔ)設(shè)施之一，城市的公共交通系統(tǒng)更加是一個城市立體動態(tài)的大系統(tǒng)中一個重要的組成部分，是城市推進(jìn)城市化發(fā)展中不可缺少的重要物質(zhì)條件和基礎(chǔ)設(shè)施產(chǎn)業(yè)，在城市規(guī)劃、經(jīng)濟(jì)發(fā)展，社會發(fā)展和人民生活中起著關(guān)鍵的作用。由此可見公共交通系統(tǒng)是聯(lián)系廣大群眾的社會生產(chǎn)、人員流通和人民生活的重要參考指標(biāo)，也是一個城市的綜合功能中不可或缺的重要組成部分。伴隨著公交線路的增多，如何選擇合理的乘坐方案的需求被廣大出行群眾們擺到了臺前，轉(zhuǎn)乘推薦系統(tǒng)也就隨之孕育而生。一個合理的轉(zhuǎn)乘推薦方案是公共交通優(yōu)先的基本保證,也是城市公共交通實現(xiàn)整體化的重要指標(biāo)之一,它對城市網(wǎng)絡(luò)結(jié)構(gòu)的完善和土地使用的合理化有著至關(guān)重要的意義。一個城市的公交系統(tǒng)一定是與城市居民的日常生活聯(lián)系最為之緊密的節(jié)點之一，甚至一個擁有優(yōu)良規(guī)劃的城市公交系統(tǒng)在一定程度上影響著城市居民的生活方式。一個好的城市公交系統(tǒng)之下必然需要一個高效且穩(wěn)定的查詢系統(tǒng)，能夠幫助廣大出行群眾快速地選擇出行線路、轉(zhuǎn)乘路線等，既要提升出行群眾選擇效率，已到達(dá)方便居民出行的目的，又可以優(yōu)城市公交在資源上的配置，進(jìn)而提高城市交通運(yùn)輸之效率和城市公交系統(tǒng)的信息服務(wù)化水平，其應(yīng)用非常廣泛。因而，時下眾多的出行軟件和地圖軟件都會將實現(xiàn)查詢公交線路中，最優(yōu)路徑查詢和最優(yōu)轉(zhuǎn)乘方案推薦作為軟件生態(tài)中最為重要的一個環(huán)節(jié)，以滿足不同用戶的需求。其中以對最優(yōu)的轉(zhuǎn)乘方案推薦最為廣大人民群眾所最迫切需要。本文將從中小城市的公交線路入手，以汕尾市城區(qū)的公交路線為研究樣本，在此基礎(chǔ)上分析中小城市公交轉(zhuǎn)乘需求、轉(zhuǎn)乘系統(tǒng)推薦方案的統(tǒng)運(yùn)行效率及其穩(wěn)定性的。通過算法優(yōu)化來實現(xiàn)實效率的提升和系統(tǒng)的穩(wěn)定，盡可能低降低影響因素帶來的負(fù)面影響。隨后對已有的最短路徑算法應(yīng)用于轉(zhuǎn)乘算法的數(shù)種算法進(jìn)行比較分析,提出一種合理的，適用于中小城市的轉(zhuǎn)乘需求的改進(jìn)算法。1.2公交站點現(xiàn)狀本文以汕尾市城區(qū)為例，遂將整個汕尾市城區(qū)的公交路線以及站點記錄下來，并按照：”公交線路—站點”的格式進(jìn)行排列。表1-1公交線路站點表1路2路3路4路霞洋客運(yùn)站v1職業(yè)技術(shù)學(xué)院A區(qū)v23輪渡v70霞洋客運(yùn)站v1海林小學(xué)v2職業(yè)技術(shù)學(xué)院B區(qū)v24二馬路口v9海林小學(xué)v2禎祥路口v3文德市場v25協(xié)興廣場v37禎祥路口v3城南路口v4奎山公園v26城內(nèi)路口v34城南路口v4市工商局v5市公安局v27海珍v71百匯市場v58新瑤社區(qū)v6華園v53小區(qū)v28華園v53吉祥路口v62微波樓v7西小區(qū)宿舍v30市國稅v54城區(qū)司法局v63一共22條路線，178個站點。（完整公交線路表詳見附錄）1.3轉(zhuǎn)乘算法現(xiàn)狀最短路徑問題是比較貼近生活的實際應(yīng)用問題。在圖中，確定了起始節(jié)點和終點節(jié)點后，一般的情況下連接兩者的路徑眾條。其中所通過的節(jié)點之間的邊或弧的距離權(quán)重值相加后最小的那一條路徑就稱為兩點之間的最短路徑，路徑上的第一個頂點起始節(jié)點，最后一個節(jié)點為終點節(jié)點。其算法的具體步驟和表達(dá)形式為：1.確定出發(fā)站點v1最短路徑問題，即已知起始的節(jié)點，求該節(jié)點之間的最短路徑的問題。[11]2.確定目標(biāo)節(jié)點Vn的最短路徑問題，與確定出發(fā)站點v1的問題相反，該問題是已知目標(biāo)節(jié)點Vn，進(jìn)而求最短路徑的問題。此問題根據(jù)圖是否具有向性而劃分為兩種情況：1.在無向圖中該問題與確定出發(fā)站點v1的問題完全等同，在有向圖中該問題等同于把所有路徑方向進(jìn)行反轉(zhuǎn)操作的確定出發(fā)站點的問題。3.確定了出發(fā)站點v1和目標(biāo)站點Vn的最短路徑問題，即已知起始節(jié)點和最終所需要到達(dá)的節(jié)點，求兩結(jié)點之間的最短路徑。用于求取最短路徑的算法有很多，本文主要著重于Dijkstra算法和floyd算法的實現(xiàn)以及優(yōu)化后的Dijkstra算法和前兩種算法在運(yùn)行效率和穩(wěn)定性上的比較。1.4課題現(xiàn)狀在我國，許多大城市隨著城市規(guī)模的擴(kuò)大，交通壓力也隨之增大，因此很早之前就提出了“出行時公交優(yōu)先”的原則，城市的交通規(guī)劃也一直在選擇更加合理的公交站點以建設(shè)良好的公交網(wǎng)絡(luò)系統(tǒng)，但由于歷史進(jìn)程和人流聚集點等一系列原因?qū)е鹿徽军c再設(shè)立時銜接的安排并不能做到盡善盡美這就導(dǎo)致了出行民眾有了公交轉(zhuǎn)乘的需求。城市新建的汽車客運(yùn)站基本時基本都會考慮并實現(xiàn)與城市原本的交通系統(tǒng)的銜接，汽車客運(yùn)站附近都配有公交汽車站，有些客運(yùn)站還與地鐵甚至做到了了無逢接駁。因此民眾出行乘坐公交，怎樣選擇更為合理的轉(zhuǎn)乘方案的需求，也日益增長。繼而促使學(xué)者們大力研究轉(zhuǎn)乘算法。2008年，中國地質(zhì)大學(xué)研究生在.net2005平臺下設(shè)計實現(xiàn)搜索引擎版MAPGIS7.1-IMS平臺中結(jié)合實際、功能全面、性能得到極大提高并方便用戶二次開發(fā)的公交轉(zhuǎn)乘功能模塊。同年數(shù)學(xué)建模大賽中一篇《乘公交，看奧運(yùn)》的作品出現(xiàn)，給出了合理的設(shè)計以及可行的公交轉(zhuǎn)乘方案。時至今日，公交轉(zhuǎn)乘算法日漸成熟，各種交通工具的轉(zhuǎn)乘，轉(zhuǎn)乘算發(fā)也越來越多的被開發(fā)出來。

第二章公交換乘系統(tǒng)2.1概述隨著城市的城市化發(fā)展，城市的公交線路也變得四通八達(dá)起來,人們的出行也是越來越便捷。然而,在現(xiàn)實生活中隨著可選的公交線路的增多,人們在眾多可選方案中,如何找出一個既能省節(jié)省大量時間又能高效地乘車,已成為出行群眾需要思考的一個重要問題。因此,各類公交車出行查詢軟件上需要一種更加穩(wěn)定高效的換乘方案推薦系統(tǒng),以此實現(xiàn)公交轉(zhuǎn)乘查詢的自動化和信息化,來提高出行群眾選著公交路線的效率，節(jié)約大量時間成本和提高城市公交的運(yùn)營效率。轉(zhuǎn)乘方案的算法設(shè)計應(yīng)從符合實際操作情況出發(fā)，以優(yōu)化查詢結(jié)果，選合適的線路為根本出發(fā)點，來滿足人們出行方便的需求。2.2公交線路2.2.1公交路線特點公共交通的線路網(wǎng)絡(luò)與道路網(wǎng)絡(luò)不同，它具有如下幾個特性(1)多個站點相互可通性連接到城市道路網(wǎng)的兩條線路的交點不一定通過公共交通網(wǎng)連接。在公共交通網(wǎng)絡(luò)中，公共交通網(wǎng)絡(luò)中有多個公共交通工具可以在同一地點交叉，但是如果交點不是公交車站，交點就不能連接到公共交通網(wǎng)絡(luò)。公共交通網(wǎng)中節(jié)點的連接狀態(tài)有3個。1.同一道路上的公共交通機(jī)關(guān)的連接；2.同一地點不同的公共交通線路的連接，通過傳輸來實現(xiàn)。3.不同點不同公共運(yùn)輸線路的連接需要多個傳輸。而且，這樣會大量地增加時間成本。(2)站點選擇性公交網(wǎng)絡(luò)在線路上會有一定的重疊路線存在，但是公交站點則不存在不同線路的公交路線其線上的站點大量重疊的情況。因此在設(shè)計換乘方案時需要對不同公交線路上站點之間的重疊進(jìn)行統(tǒng)計和分析。在實際的換乘中，需要在不同的公交線路之間換乘公交車到達(dá)目的地，這就要求節(jié)點上相應(yīng)網(wǎng)絡(luò)圖的不同屬性之間的連接，而這也正是公交網(wǎng)絡(luò)分析的重要意義所在。在公交線網(wǎng)疊置分析中，需要合理地將空間相近的不同線站抽象成圖上的相關(guān)節(jié)點，以模擬不同公交線之間的互換情況。(3)空間定點位置屬性[9]同一道路上運(yùn)行的不同公交線路在運(yùn)行過程中有部分重疊，但其車站不能完全重疊。因此，在公交線網(wǎng)分析中，需要根據(jù)一定的原則，將空間上適當(dāng)距離內(nèi)不同線路附近同名車站抽象成網(wǎng)絡(luò)圖上的相關(guān)節(jié)點，以模擬不同公交線網(wǎng)之間的變化情況。(4)一對多屬性在公共交通網(wǎng)絡(luò)中，節(jié)點與屬性的關(guān)系是一對多的。同一車站在路網(wǎng)中具有相同的空間位置和屬性，由于其在不同公交線路上的位置不同，可能具有不同的屬性和權(quán)重。在公交網(wǎng)絡(luò)的描述中，節(jié)點權(quán)重函數(shù)可以用來設(shè)置不同的值來模擬實際情況。2.3路徑問題由于交通線網(wǎng)的一些特殊性質(zhì)，如：線網(wǎng)中的最短路徑問題，乘客并不關(guān)心路徑的長度，而是關(guān)心從始發(fā)地到目的地所耗費的時間是否最短，因為全國大多數(shù)城市的公交票價是統(tǒng)一的，人們關(guān)心的不是車輛行駛了多少路（因為它與乘客無關(guān)），而是時間長度。而且，行車時間與道路長度不成正比，這也受到很多外部因素的影響，比如：道路是否暢通？轉(zhuǎn)車方便嗎？你轉(zhuǎn)車時需要步行嗎？這條線路在我實際等待的時間頻段內(nèi)發(fā)車以及經(jīng)過我等待站點的頻率如何？等待最近一班公交車的到來需要多長時間等等都會嚴(yán)重影響到出行的總體時間。在轉(zhuǎn)乘的過程中往往需要我們步行移動到下一個站點，這其中又會產(chǎn)生需要等待公交車到來的時間成本。因此，盡可能少的減少換乘次數(shù)就可以為出行群眾節(jié)約下大量的時間。例如1路公交車從出發(fā)站點V1到目標(biāo)站點V9所需要的車程為30分鐘至40分鐘之間，而通過中間站點V17做一次轉(zhuǎn)乘可在20分鐘內(nèi)到達(dá)。通常乘客們才會考慮選擇該轉(zhuǎn)乘方案，否則最優(yōu)路線等于最小換乘次數(shù)。

2.4轉(zhuǎn)乘算法實現(xiàn)2.4.1最少轉(zhuǎn)乘原則出發(fā)站點與目的站點之間有直線到達(dá)的，應(yīng)該直接選擇直線到達(dá)方案，不再去考慮其他方案。但在實際生活中，從出發(fā)站點出發(fā)，到達(dá)目地站點總會出現(xiàn)是需要通過路線換乘才能到達(dá)的情況，而如果需要轉(zhuǎn)乘一次就能到達(dá)目的站點則可考慮選擇該方案作為出行方案；若是由于路況和線路規(guī)劃原因需要轉(zhuǎn)乘兩次才能到達(dá)目的站點，也可考慮該方案為出行方案；實際情況中，我們一般不會考慮需要轉(zhuǎn)乘三次或者三次以上的轉(zhuǎn)乘方案，因此三次或者三次以上轉(zhuǎn)乘的線路為了方便數(shù)據(jù)比較只會出現(xiàn)在實驗中，而三次或者三次以上的轉(zhuǎn)乘方案是不在本文的轉(zhuǎn)乘推薦算法的考慮范圍內(nèi)。2.4.2Dijkstra算法圖2-1有向路徑權(quán)重圖Dijkstra算法是一種要求運(yùn)算過程中找出圖中全部的非負(fù)邊的貪心單源最短路徑算法。在Dijkstra算法中，需要用一個鄰接矩陣來存節(jié)點以及節(jié)點之間的距離權(quán)重值。表2-1權(quán)值鄰接矩陣表arrayV1V2V3V4V5V10112xxV2x093xV3xx0x5V4xx4013V5xxxx0在運(yùn)算的過程中我們需要一個一維數(shù)組來記錄源點v1到達(dá)各個節(jié)點的初始路徑的權(quán)重值。表2-2V1出度表PMV1V2V3V4V5V10112xx通過觀察我們可以得知，距離v1最近的節(jié)點是v2，而v2前進(jìn)到達(dá)的點分別為v3，v4，v5。其中我們通過比較PM[v3]和PM[V2]+array[V2][V3]的大小來確認(rèn)v1到達(dá)v3的權(quán)重值是多少來決定v1到達(dá)v2的最短路徑為多少。其中PM[v2]表示v1到達(dá)v2的距離大小，array[v2][v3]表示v2到達(dá)v3的路徑大小。PM[V3]=12,PM[V2]+array[V2][V3]=1+9=10，PM[V3]>PM[V2]+array[V2][V3]，即PM[V3]通過松弛應(yīng)該更新為10，v1到達(dá)v3的路徑即為PM[V3]=10。同理，通過松動PM[V4]=4,PM[V5]=13。Dijkstra算法就是每次通過尋找距離源節(jié)點最近的一個節(jié)點，然后通過該節(jié)點計算所有該節(jié)點能到達(dá)的節(jié)點的路徑權(quán)重值，每找一次通過與上次的最小路徑的權(quán)重值進(jìn)行比較，若小，則松弛一次。最終找到源節(jié)點到達(dá)目標(biāo)節(jié)點的最短路徑。代碼如下：publicvoiddijkstra(intp){int[]d=newint[n];Set<Integer>set=newHashSet<>(n);set.add(p);for(inti=0;i<n;i++){d[i]=a[p][i];}while(set.size()<n){intle=Integer.MAX_VALUE;intnum=0;for(inti=0;i<n;i++){if(!set.contains(i)&&le>d[i]){le=d[i];num=i;}}for(inti=0;i<n;i++){if(!set.contains(i)){d[i]=Math.min(d[i],d[num]+a[num][i]);}}set.add(num);}for(inti=0;i<n;i++){System.out.println("點"+p+"到點"+i+"的距離為："+d[i]);}}2.4.3弗洛伊德算法弗洛伊德算法（floyd）是一種基于動態(tài)規(guī)劃的多源最短路徑算法。代碼如下：for(k=0;k<mgraph.n;k++) { for(v=0;v<mgraph.n;v++) { for(w=0;w<mgraph.n;w++) { if(shortPathTable[v][w]>shortPathTable[v][k]+shortPathTable[k][w]) { shortPathTable[v][w]=shortPathTable[v][k]+shortPathTable[k][w]; pathMatirx[v][w]=pathMatirx[v][k]; } } } }Flovd算法是通過三次循環(huán)和一次節(jié)點更新來完成的，flovd算法之所以能通過如此之簡短的代碼實現(xiàn)最短路徑的選擇，主要是通過動態(tài)規(guī)劃來實現(xiàn)的。而動態(tài)規(guī)劃中最重要的兩個部分則是節(jié)點狀態(tài)的定義和節(jié)點在選擇前進(jìn)路徑時所在于的階段。如節(jié)點array[i][j][k]是可以由array[i-1][j][k]這個不經(jīng)過第i個節(jié)點移動而來的，也可以是由array[i-1][j][i]到達(dá)array[i-1][i][k]這個經(jīng)過第i個節(jié)點的階段而來。Flovd算法通過監(jiān)測這個狀態(tài)的過程，判斷是否會滿足圖的最優(yōu)子結(jié)構(gòu)和是否滿足無后性。若結(jié)果符合最優(yōu)子結(jié)構(gòu)且符合無后效性，則路徑為最短路徑。其中，最優(yōu)子結(jié)構(gòu)的定義為最短路徑的任意子路徑依然為最短路徑。即一條路徑上有五個節(jié)點：vi(i=1,2,3,4,5)。五個節(jié)點組成一條按照順序排列的有向路徑剛好為v1到達(dá)v5的最短路徑，即v1->v2->v3->v4->v5,則v3->v4->v5一定是v3經(jīng)過v4到達(dá)v5的最短路徑。如果一條最短路徑要經(jīng)過節(jié)點v2，那么出發(fā)節(jié)點到v2的最短路徑加上v2到目標(biāo)節(jié)點的最短路徑一定是出發(fā)節(jié)點要經(jīng)過v2節(jié)點到達(dá)目標(biāo)節(jié)點的最短路徑。無后效性是指節(jié)點array[i][j][k]由array[i-1][j][k]，array[i-1][j][i]，array[i-1][i][k]轉(zhuǎn)移過來的這個過程中，k始終是最外層循環(huán)。Floyd算法在求最短路徑時，需要通過一個臨時數(shù)組來記錄出發(fā)節(jié)點到達(dá)目標(biāo)節(jié)點的過程中經(jīng)過的中間節(jié)點，即v3->path[v1][v5]->v5->path[v5][v3]->v5然后求path[v3][v5]和path[v5][v3]，一直到v3和v5之間沒有中間節(jié)點為止。代碼如下：int[][]shortPathTable=newint[9][9]; int[][]pathMatirx=newint[9][9]; intv,w,k; for(v=0;v<mgraph.n;v++) { for(w=0;w<mgraph.n;w++) { shortPathTable[v][w]=mgraph.edges[v][w]; pathMatirx[v][w]=w; } }圖2-2弗洛伊德算法權(quán)限圖

2.4.4算法改進(jìn)在以上兩個最短路徑算法中我們不難看出，算法的時間復(fù)雜度為O（n），該算法遍歷一次有向圖所求到最短路徑需要調(diào)用n次，那么時間復(fù)雜度即為O（n^3）。其中內(nèi)循環(huán)是用來找出出發(fā)節(jié)點到達(dá)目標(biāo)節(jié)點所經(jīng)過的中間節(jié)點，即使通過優(yōu)先隊列對其進(jìn)行算法的優(yōu)化一旦需要運(yùn)算的數(shù)據(jù)過大，優(yōu)化效果也不大。再深入的觀察后，我們發(fā)現(xiàn)對于換乘方案，站點間的距離，即節(jié)點之間的邊的權(quán)值的影響較小，我們只需要明確起點站點和終點站點之間，是否存在一條公交線路使得我們能夠直達(dá)，或是是否存在一個或兩個中間站點，使得我們能通過一次或者兩次換乘到達(dá)目的地即可。于是本文從鄰接矩陣能用于求圖節(jié)點之間是否能相互連通的特點入手，通過求矩陣的平方來完成一次換乘的功能，通過求矩陣的立方完成二次換乘的功能。第三章程序?qū)崿F(xiàn)3.1概念結(jié)構(gòu)設(shè)計（1）確定出發(fā)站點v1和目標(biāo)站點Vn；查詢所有經(jīng)過站點v1和站點Vn的所有公交線路。（2）查詢是否存在中間節(jié)點Vi使得V1到達(dá)Vi,Vi到達(dá)Vn,如果存在節(jié)點Vi，則表示從發(fā)站點v1和目標(biāo)站點Vn有直達(dá)車，將結(jié)果輸出后程序結(jié)束，若不存在中間節(jié)點Vi，則執(zhí)行下一步；（3）將汕尾市城區(qū)的公交站點按照順序轉(zhuǎn)換為鄰接矩陣；（4）在鄰接矩陣中確定出發(fā)站點V1和目標(biāo)站點Vn；（5）在鄰接矩陣中尋找一個節(jié)點Vi，使得出發(fā)站點可以到達(dá)Vi，而Vi可以到達(dá)目標(biāo)站點Vn；實現(xiàn)一次換乘到達(dá)目的地。若不能則進(jìn)入下一步；（6）在鄰接矩陣中尋找兩個站點Vi和Vj，使得出發(fā)站點v1可以到達(dá)站點Vi，站點vi可以到達(dá)站點Vj，站點Vj可以到達(dá)目標(biāo)站點Vn；實現(xiàn)兩次換乘到達(dá)目的地。若不能則進(jìn)入下一步；（7）在鄰接矩陣中尋找多個站點Vi（i=正整數(shù)），使得出發(fā)站點v1通過中間多個站點Vi（i=正整數(shù)）可以到達(dá)目標(biāo)站點Vn；實現(xiàn)多次換乘到達(dá)目的地。直到找出最短路徑。若遍歷過整個鄰接矩陣，則直接退出程序，提示用戶檢查發(fā)站點v1和目標(biāo)站點Vn是否正確。

3.2數(shù)據(jù)錄入站點以站路順序排列，為方便測試，以vi(i=1,2,3…n)(i為整數(shù))的形式命名。表3-1部分站點的數(shù)字站點由百度地圖中的路程比例得出路徑的權(quán)重值。圖3-1路公交車的路線圖中比例為1：50，即途中1厘米為現(xiàn)實中500米，我們約定每100米的距離記其路徑權(quán)重為1?？傻玫较卤恚罕?-2V1線路權(quán)值表（部分）V1V2V3V4V5V1086553.3算法實現(xiàn)3.3.1矩陣的定義與生成以輸入的兩個站點中的第一個為起點，找出站點二維數(shù)組中，所有的存在起點的行，遍歷該行中是否存在第二個站點，即終點。若存在，即為1，若不存在，即為0。（1）判斷站點是否在同一公交線路上publicclassBusStop{ publicstaticvoidmain(String[]args){ int[]busline1={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}; int[]busline2={23,24,25,26,27,28,29,30,31,32,33,34,35,36,11,12,37,38,39,40,41,42,43,44,45}; int[]busline3={46,47,36,33,48,49,50,51,52,53,54,55,56,57}; int[]busline4={1,2,3,4,58,59,60,61,28,27,26,62,63,64,65,20,66,21,67}; int[]busline6={1,2,3,4,5,6,7,8,9,10,11,12,68,69,70,62,51,71,72,18,19,21,73}; int[]busline7={67,74,75,21,66,20,65,64,76,63,62,77,78,30,31,79,80,36,10,9,81,46,82,83}; int[]busline8={1,2,3,4,58,59,84,79,85,37,13,14,15,16,17,18,86,21,87,74}; int[]busline9={1,2,3,4,5,6,7,8,9,10,11,12,68,69,88,89,90,71,72,18,19,20,21,22}; int[]busline10={91,7,8,9,10,36,80,79,31,92,78,93,62,63,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111}; int[]busline11={1,2,3,4,5,112,33,32,79,113,77,62,63,114,96,97,98,73}; int[]busline12={52,115,116,117,118,119,120,36,121,122,123,1,124,125,126}; int[]busline13={91,123,122,121,36,127,128,48,129,130,131,98,132,133,134}; int[]busline102={75,64,65,20,66,86,18,72,71,90,89,88,69,68,12,11,10,9,135,136,137,138}; int[]busline105={46,81,9,10,36,35,34,33,32,79,113,77,62,63,114,139}; int[]busline106={140,141,142,143,144,145,26,146,147,17,18,19,21,148}; int[]busline107={149,150,151,152,153,58,5,6,154,35,36,155,156,157,158,159,160,44,45}; int[]busline108={91,46,83,45,44,43,161,14,15,16,162,163,164,74,73}; int[]busline111={140,141,142,143,144,27,26,146,147,90,165,166,66,21,167,168,169,96,97,98,99,100,101,102,103,104,105,106,107,108}; int[]busline112={1,2,3,4,5,112,33,32,31,30,29,28,27,26,62,63,64,65,20,66,21,73}; int[]busline114={170,171,172,28,61,60,84,32,33,112,6,154,36,11,12,37,13,14,15,16,17,173,164,74}; int[]busline117={75,64,65,20,66,86,18,17,16,15,14,13,38,39,174,175,159,43,44,45,83}; int[]busline176={176,56,55,54,52,94,63,117,177,178,122}; inta=1; intb=2; useLoop(busline1,a,b); } publicstaticvoiduseLoop(int[]arr,inta,intb){ /* for(inti=0;i<arr.length;i++){ System.out.print(arr[i]+""); } System.out.println(); */ if(line1(arr,a)==line2(arr,b)){ System.out.print(1); }else{ System.out.print(0); } } publicstaticintline1(int[]arr,inta){ intnum=3; for(inti=0;i<arr.length;i++){ if(a==arr[i]){ num=1; break; }else{ num=0; } break; } returnnum; } publicstaticintline2(int[]arr,intb){ intnum=3; for(inti=0;i<arr.length;i++){ if(b==arr[i]){ num=1; break; }else{ num=0; } break; } returnnum; }}（2）錄入站點矩陣（168*168）數(shù)據(jù)上面我們通過判斷兩個站點之間是否在同一線路上，來找出兩個站點之間是否存在直達(dá)線路，若兩個站點之間能直達(dá)，則記為1，否者記為0。并將結(jié)果錄入到由168個站點組成的大矩陣中。 //公交站點的矩陣 staticint[][]edges=newint[178][178];//判斷是存在一條路線，同時有站點1，站點2 publicstaticintsuan(inti,intj){ intnum=3; for(intk=0;k<22;k++){ if(useLoop(busline[k],i,j)==1){ num=1; break; }else{ num=0; } } returnnum; } //判斷兩個站點是否在同一條線路上 publicstaticintuseLoop(int[]arr,inta,intb){ intnum=3; if(line1(arr,a)==1&&line2(arr,b)==1){ num=1; }else{ num=0; } returnnum; } publicstaticintline1(int[]arr,inta){ intnum=3; for(inti=0;i<arr.length;i++){ if(a==arr[i]){ num=1; break; }else{ num=0; } } returnnum; } publicstaticintline2(int[]arr,intb){ intnum=3; for(inti=0;i<arr.length;i++){ if(b==arr[i]){ num=1; break; }else{ num=0; } } returnnum; } //鄰接矩陣的賦值 staticvoidline(){ for(inti=0;i<178;i++) { for(intj=0;j<178;j++) { edges[i][j]=suan(i+1,j+1); } } } //打印鄰接矩陣 staticvoiddaYin(){ line(); for(inti=0;i<178;i++){ for(intj=0;j<178;j++){ System.out.print(edges[i][j]); } System.out.println(); } }這里以26*26的小矩陣來表示站點1到16之間的連通情況，測試程序的準(zhǔn)確性，完整的矩陣詳情見附錄（矩陣.txt）文件。圖3-126*26的鄰接矩陣（3）矩陣的冪次方計算//考慮冪為0的時候，計算結(jié)果為鄰接矩陣，值為1即為可直達(dá) if(n==0){ for(inti=0;i<m;i++){ for(intj=0;j<m;j++){ if(i==j){ System.out.print(1+"");//對角線為1 } else{ System.out.print(0+""); } } System.out.println(); } } //輸出能直達(dá)的線路 elseif(n==1){ for(inti=0;i<m;i++){ for(intj=0;j<m;j++){ System.out.print(a[i][j]+""); } System.out.println(); } } //冪大于1時 else{ for(intz=1;z<n;z++){ long[][]tmp=newlong[m][m]; for(inti=0;i<m;i++){ for(intj=0;j<m;j++){ longc=0; for(intk=0;k<m;k++){ c+=a[i][k]*b[k][j];//第一個矩陣的每一行的每個數(shù)乘以第二個矩陣的每一列的每個數(shù)相加 } tmp[i][j]=c; } } b=tmp; } for(inti=0;i<m;i++){ for(intj=0;j<m;j++){ System.out.print(b[i][j]+"");//輸出結(jié)果 } System.out.println(); } }（4）優(yōu)化矩陣運(yùn)算在使用矩陣進(jìn)行求平方和求立方時，往往是講整個矩陣進(jìn)行遍歷，這樣會消耗大量內(nèi)存，使得運(yùn)行效率不高效。通過觀察我們不難看出，我們只需要找出起點和中間之間，是否存在一個或者兩個中間節(jié)點使得起點能通過一次或二次換乘到達(dá)。因此，我們只要確定起點，找出所有含有起點的線路，即存儲站點信息的二維數(shù)組中存在起點的行，遍歷該行中的所有元素，查找是否有和終點在同一行的元素存在，即中間節(jié)點是否存在，若存在則能通過一次換乘到達(dá)。相對的，找出存儲站點信息的二維數(shù)組中存在起點的行，遍歷該行中的所有站點，并以每個站點為“新起點”，通過遍歷“新起點”，查找新起點所在的行中，是否有和終點在同一行的站點存在，若存在，即起點能通過兩個中間節(jié)點，到達(dá)終點，完成兩次轉(zhuǎn)乘到達(dá)目的地。 //轉(zhuǎn)乘可到達(dá)目的地 staticvoidtransfer(inta,intb){ if(edges[a-1][b-1]!=1){//一次轉(zhuǎn)乘 for(inti=0;i<busline.length;i++){ if(line1(busline[i],a)==1){ for(intj=0;j<busline[i].length;j++){ if(useLoop(busline[j],busline[i][j],b)==1){ System.out.println("乘坐"+(i+1)+"路公交車,轉(zhuǎn)"+(j+1)+"路公交可到達(dá)目的地"); }else{ break; } //System.out.print(busline[i][j]+""); break; } } } }elseif(edges[a-1][b-1]!=1){//二次轉(zhuǎn)乘 for(inti=0;i<busline.length;i++){ if(line1(busline[i],a)!=1){ for(intj=0;j<busline[i].length;j++){ if(useLoop(busline[j],busline[i][j],b)!=1){ for(intk=0;j<busline[j].length;k++){ if(useLoop(busline[k],busline[j][k],b)==1){ System.out.println("乘坐"+(i+1)+"路公交車,轉(zhuǎn)"+(j+1)+"再轉(zhuǎn)"+(k+1)+"路公交可到達(dá)目的地"); } } }else{ System.out.println("不可在兩次換乘中達(dá)到，建議選擇其他交通工具"); break; } break; } //System.out.println(); } } }else{//直達(dá) for(inti=0;i<busline.length;i++){ if(useLoop(busline[i],a,b)==1){ System.out.println("乘坐"+(i+1)+"路公交車能直達(dá)目的地"); } } } }

第四章分析檢驗4.1測試類4.1.1Floyd與Dijkstra publicclassTest{ publicstaticvoidmain(String[]args) { MGraphmg=newMGraph(); int[][]array=newint[9][9]; for(inti=0;i<9;i++) for(intj=0;j<9;j++) array[i][j]=MGraph.NULL; array[0][1]=1; array[1][0]=1; array[0][2]=5; array[2][0]=5; array[1][2]=3; array[2][1]=3; array[1][3]=7; array[3][1]=7; array[3][4]=2; array[4][3]=2; array[1][4]=5; array[4][1]=5; array[2][4]=1; array[4][2]=1; array[2][5]=7; array[5][2]=7; array[4][5]=3; array[5][4]=3; array[3][6]=3; array[6][3]=3; array[4][6]=6; array[6][4]=6; array[4][7]=9; array[7][4]=9; array[5][7]=5; array[7][5]=5; array[6][7]=2; array[7][6]=2; array[6][8]=7; array[8][6]=7; array[7][8]=4; array[8][7]=4; CreateMgraphcm=newCreateMgraph(); cm.createMat(mg,array,9); cm.DispMat(mg); Dijkstra.dijkstra(mg,0); Floyd.floyd(mg);}publicclassTestLinJie{ publicstaticvoidmain(String[]args){ BusStopDirectlinjie=newBusStopDirect(); linjie.line();//進(jìn)行矩陣賦值 linjie.daYin();//輸出鄰接矩陣 linjie.transfer(1,22); linjie.transfer(2,17); linjie.transfer(119,3); }}

4.1.2鄰接矩陣publicclassTestLinJie{ publicstaticvoidmain(String[]args){ BusStopDirectlinjie=newBusStopDirect(); linjie.line();//進(jìn)行矩陣賦值 linjie.daYin();//輸出鄰接矩陣 linjie.transfer(1,22); linjie.transfer(28,17); linjie.transfer(119,3); }4.2實驗結(jié)果4.2.1Dijkstra算法-15------1-375----53--17----7--2-3---512-369---7-3--5----36--27----952-4------74-Dijkstra算法求得最短路徑:1->0->2->1->0->3->4->2->1->0->4->2->1->0->5->4->2->1->0->6->3->4->2->1->0->7->6->3->4->2->1->0->8->7->6->3->4->2->1->0->4.2.2弗洛伊德算法-15------1-375----53--1-----7--2-----512-----------------------------------------Floyd算法求得最短路徑：v0->Aweight:1path:0->1v0->v2weight:4path:0->1->2v0->v3weight:7path:0->1->2->4->3v0->v4weight:5path:0->1->2->4v0->v5weight:1000path:0->5v0->v6weight:1000path:0->6v0->v7weight:1000path:0->7v0->v8weight:1000path:0->8A->v2weight:3path:1->2A->v3weight:6path:1->2->4->3A->v4weight:4path:1->2->4A->v5weight:1000path:1->5A->v6weight:1000path:1->6A->v7weight:1000path:1->7A->v8weight:1000path:1->8v2->v3we