廣東省中小城市公交線路評(píng)估

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

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

2.4轉(zhuǎn)乘算法實(shí)現(xiàn)2.4.1最少轉(zhuǎn)乘原則出發(fā)站點(diǎn)與目的站點(diǎn)之間有直線到達(dá)的，應(yīng)該直接選擇直線到達(dá)方案，不再去考慮其他方案。但在實(shí)際生活中，從出發(fā)站點(diǎn)出發(fā)，到達(dá)目地站點(diǎn)總會(huì)出現(xiàn)是需要通過路線換乘才能到達(dá)的情況，而如果需要轉(zhuǎn)乘一次就能到達(dá)目的站點(diǎn)則可考慮選擇該方案作為出行方案；若是由于路況和線路規(guī)劃原因需要轉(zhuǎn)乘兩次才能到達(dá)目的站點(diǎn)，也可考慮該方案為出行方案；實(shí)際情況中，我們一般不會(huì)考慮需要轉(zhuǎn)乘三次或者三次以上的轉(zhuǎn)乘方案，因此三次或者三次以上轉(zhuǎn)乘的線路為了方便數(shù)據(jù)比較只會(huì)出現(xiàn)在實(shí)驗(yàn)中，而三次或者三次以上的轉(zhuǎn)乘方案是不在本文的轉(zhuǎn)乘推薦算法的考慮范圍內(nèi)。2.4.2Dijkstra算法圖2-1有向路徑權(quán)重圖Dijkstra算法是一種要求運(yùn)算過程中找出圖中全部的非負(fù)邊的貪心單源最短路徑算法。在Dijkstra算法中，需要用一個(gè)鄰接矩陣來存節(jié)點(diǎn)以及節(jié)點(diǎn)之間的距離權(quán)重值。表2-1權(quán)值鄰接矩陣表arrayV1V2V3V4V5V10112xxV2x093xV3xx0x5V4xx4013V5xxxx0在運(yùn)算的過程中我們需要一個(gè)一維數(shù)組來記錄源點(diǎn)v1到達(dá)各個(gè)節(jié)點(diǎn)的初始路徑的權(quán)重值。表2-2V1出度表PMV1V2V3V4V5V10112xx通過觀察我們可以得知，距離v1最近的節(jié)點(diǎn)是v2，而v2前進(jìn)到達(dá)的點(diǎn)分別為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。同理，通過松動(dòng)PM[V4]=4,PM[V5]=13。Dijkstra算法就是每次通過尋找距離源節(jié)點(diǎn)最近的一個(gè)節(jié)點(diǎn)，然后通過該節(jié)點(diǎn)計(jì)算所有該節(jié)點(diǎn)能到達(dá)的節(jié)點(diǎn)的路徑權(quán)重值，每找一次通過與上次的最小路徑的權(quán)重值進(jìn)行比較，若小，則松弛一次。最終找到源節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最短路徑。代碼如下：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("點(diǎn)"+p+"到點(diǎn)"+i+"的距離為："+d[i]);}}2.4.3弗洛伊德算法弗洛伊德算法（floyd）是一種基于動(dòng)態(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é)點(diǎn)更新來完成的，flovd算法之所以能通過如此之簡(jiǎn)短的代碼實(shí)現(xiàn)最短路徑的選擇，主要是通過動(dòng)態(tài)規(guī)劃來實(shí)現(xiàn)的。而動(dòng)態(tài)規(guī)劃中最重要的兩個(gè)部分則是節(jié)點(diǎn)狀態(tài)的定義和節(jié)點(diǎn)在選擇前進(jìn)路徑時(shí)所在于的階段。如節(jié)點(diǎn)array[i][j][k]是可以由array[i-1][j][k]這個(gè)不經(jīng)過第i個(gè)節(jié)點(diǎn)移動(dòng)而來的，也可以是由array[i-1][j][i]到達(dá)array[i-1][i][k]這個(gè)經(jīng)過第i個(gè)節(jié)點(diǎn)的階段而來。Flovd算法通過監(jiān)測(cè)這個(gè)狀態(tài)的過程，判斷是否會(huì)滿足圖的最優(yōu)子結(jié)構(gòu)和是否滿足無后性。若結(jié)果符合最優(yōu)子結(jié)構(gòu)且符合無后效性，則路徑為最短路徑。其中，最優(yōu)子結(jié)構(gòu)的定義為最短路徑的任意子路徑依然為最短路徑。即一條路徑上有五個(gè)節(jié)點(diǎn)：vi(i=1,2,3,4,5)。五個(gè)節(jié)點(diǎn)組成一條按照順序排列的有向路徑剛好為v1到達(dá)v5的最短路徑，即v1->v2->v3->v4->v5,則v3->v4->v5一定是v3經(jīng)過v4到達(dá)v5的最短路徑。如果一條最短路徑要經(jīng)過節(jié)點(diǎn)v2，那么出發(fā)節(jié)點(diǎn)到v2的最短路徑加上v2到目標(biāo)節(jié)點(diǎn)的最短路徑一定是出發(fā)節(jié)點(diǎn)要經(jīng)過v2節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最短路徑。無后效性是指節(jié)點(diǎn)array[i][j][k]由array[i-1][j][k]，array[i-1][j][i]，array[i-1][i][k]轉(zhuǎn)移過來的這個(gè)過程中，k始終是最外層循環(huán)。Floyd算法在求最短路徑時(shí)，需要通過一個(gè)臨時(shí)數(shù)組來記錄出發(fā)節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的過程中經(jīng)過的中間節(jié)點(diǎn)，即v3->path[v1][v5]->v5->path[v5][v3]->v5然后求path[v3][v5]和path[v5][v3]，一直到v3和v5之間沒有中間節(jié)點(diǎn)為止。代碼如下：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)在以上兩個(gè)最短路徑算法中我們不難看出，算法的時(shí)間復(fù)雜度為O（n），該算法遍歷一次有向圖所求到最短路徑需要調(diào)用n次，那么時(shí)間復(fù)雜度即為O（n^3）。其中內(nèi)循環(huán)是用來找出出發(fā)節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)所經(jīng)過的中間節(jié)點(diǎn)，即使通過優(yōu)先隊(duì)列對(duì)其進(jìn)行算法的優(yōu)化一旦需要運(yùn)算的數(shù)據(jù)過大，優(yōu)化效果也不大。再深入的觀察后，我們發(fā)現(xiàn)對(duì)于換乘方案，站點(diǎn)間的距離，即節(jié)點(diǎn)之間的邊的權(quán)值的影響較小，我們只需要明確起點(diǎn)站點(diǎn)和終點(diǎn)站點(diǎn)之間，是否存在一條公交線路使得我們能夠直達(dá)，或是是否存在一個(gè)或兩個(gè)中間站點(diǎn)，使得我們能通過一次或者兩次換乘到達(dá)目的地即可。于是本文從鄰接矩陣能用于求圖節(jié)點(diǎn)之間是否能相互連通的特點(diǎn)入手，通過求矩陣的平方來完成一次換乘的功能，通過求矩陣的立方完成二次換乘的功能。第三章程序?qū)崿F(xiàn)3.1概念結(jié)構(gòu)設(shè)計(jì)（1）確定出發(fā)站點(diǎn)v1和目標(biāo)站點(diǎn)Vn；查詢所有經(jīng)過站點(diǎn)v1和站點(diǎn)Vn的所有公交線路。（2）查詢是否存在中間節(jié)點(diǎn)Vi使得V1到達(dá)Vi,Vi到達(dá)Vn,如果存在節(jié)點(diǎn)Vi，則表示從發(fā)站點(diǎn)v1和目標(biāo)站點(diǎn)Vn有直達(dá)車，將結(jié)果輸出后程序結(jié)束，若不存在中間節(jié)點(diǎn)Vi，則執(zhí)行下一步；（3）將汕尾市城區(qū)的公交站點(diǎn)按照順序轉(zhuǎn)換為鄰接矩陣；（4）在鄰接矩陣中確定出發(fā)站點(diǎn)V1和目標(biāo)站點(diǎn)Vn；（5）在鄰接矩陣中尋找一個(gè)節(jié)點(diǎn)Vi，使得出發(fā)站點(diǎn)可以到達(dá)Vi，而Vi可以到達(dá)目標(biāo)站點(diǎn)Vn；實(shí)現(xiàn)一次換乘到達(dá)目的地。若不能則進(jìn)入下一步；（6）在鄰接矩陣中尋找兩個(gè)站點(diǎn)Vi和Vj，使得出發(fā)站點(diǎn)v1可以到達(dá)站點(diǎn)Vi，站點(diǎn)vi可以到達(dá)站點(diǎn)Vj，站點(diǎn)Vj可以到達(dá)目標(biāo)站點(diǎn)Vn；實(shí)現(xiàn)兩次換乘到達(dá)目的地。若不能則進(jìn)入下一步；（7）在鄰接矩陣中尋找多個(gè)站點(diǎn)Vi（i=正整數(shù)），使得出發(fā)站點(diǎn)v1通過中間多個(gè)站點(diǎn)Vi（i=正整數(shù)）可以到達(dá)目標(biāo)站點(diǎn)Vn；實(shí)現(xiàn)多次換乘到達(dá)目的地。直到找出最短路徑。若遍歷過整個(gè)鄰接矩陣，則直接退出程序，提示用戶檢查發(fā)站點(diǎn)v1和目標(biāo)站點(diǎn)Vn是否正確。

3.2數(shù)據(jù)錄入站點(diǎn)以站路順序排列，為方便測(cè)試，以vi(i=1,2,3…n)(i為整數(shù))的形式命名。表3-1部分站點(diǎn)的數(shù)字站點(diǎn)由百度地圖中的路程比例得出路徑的權(quán)重值。圖3-1路公交車的路線圖中比例為1：50，即途中1厘米為現(xiàn)實(shí)中500米，我們約定每100米的距離記其路徑權(quán)重為1。可得到下表：表3-2V1線路權(quán)值表（部分）V1V2V3V4V5V1086553.3算法實(shí)現(xiàn)3.3.1矩陣的定義與生成以輸入的兩個(gè)站點(diǎn)中的第一個(gè)為起點(diǎn)，找出站點(diǎn)二維數(shù)組中，所有的存在起點(diǎn)的行，遍歷該行中是否存在第二個(gè)站點(diǎn)，即終點(diǎn)。若存在，即為1，若不存在，即為0。（1）判斷站點(diǎn)是否在同一公交線路上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）錄入站點(diǎn)矩陣（168*168）數(shù)據(jù)上面我們通過判斷兩個(gè)站點(diǎn)之間是否在同一線路上，來找出兩個(gè)站點(diǎn)之間是否存在直達(dá)線路，若兩個(gè)站點(diǎn)之間能直達(dá)，則記為1，否者記為0。并將結(jié)果錄入到由168個(gè)站點(diǎn)組成的大矩陣中。 //公交站點(diǎn)的矩陣 staticint[][]edges=newint[178][178];//判斷是存在一條路線，同時(shí)有站點(diǎn)1，站點(diǎn)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; } //判斷兩個(gè)站點(diǎn)是否在同一條線路上 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的小矩陣來表示站點(diǎn)1到16之間的連通情況，測(cè)試程序的準(zhǔn)確性，完整的矩陣詳情見附錄（矩陣.txt）文件。圖3-126*26的鄰接矩陣（3）矩陣的冪次方計(jì)算//考慮冪為0的時(shí)候，計(jì)算結(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+"");//對(duì)角線為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時(shí) 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];//第一個(gè)矩陣的每一行的每個(gè)數(shù)乘以第二個(gè)矩陣的每一列的每個(gè)數(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)行求平方和求立方時(shí)，往往是講整個(gè)矩陣進(jìn)行遍歷，這樣會(huì)消耗大量?jī)?nèi)存，使得運(yùn)行效率不高效。通過觀察我們不難看出，我們只需要找出起點(diǎn)和中間之間，是否存在一個(gè)或者兩個(gè)中間節(jié)點(diǎn)使得起點(diǎn)能通過一次或二次換乘到達(dá)。因此，我們只要確定起點(diǎn)，找出所有含有起點(diǎn)的線路，即存儲(chǔ)站點(diǎn)信息的二維數(shù)組中存在起點(diǎn)的行，遍歷該行中的所有元素，查找是否有和終點(diǎn)在同一行的元素存在，即中間節(jié)點(diǎn)是否存在，若存在則能通過一次換乘到達(dá)。相對(duì)的，找出存儲(chǔ)站點(diǎn)信息的二維數(shù)組中存在起點(diǎn)的行，遍歷該行中的所有站點(diǎn)，并以每個(gè)站點(diǎn)為“新起點(diǎn)”，通過遍歷“新起點(diǎn)”，查找新起點(diǎn)所在的行中，是否有和終點(diǎn)在同一行的站點(diǎn)存在，若存在，即起點(diǎn)能通過兩個(gè)中間節(jié)點(diǎn)，到達(dá)終點(diǎn)，完成兩次轉(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á)目的地"); } } } }

第四章分析檢驗(yàn)4.1測(cè)試類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實(shí)驗(yàn)結(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