基于dijwsrap的最短路徑算法的研究

基于dijwsrap的最短路徑算法的研究

0最短路徑求解交通堵塞問題已成為世界上最嚴重的社會、經(jīng)濟和環(huán)境問題之一。在出行前得到一條最優(yōu)路徑,使得從出發(fā)地到達目的地的時間最短,既有利于人們提高辦事效率,又能很大程度地減輕交通壓力。在路徑規(guī)劃中,可采用各種路徑優(yōu)化標準。一條路徑的好壞取決于許多因素,例如行駛距離、行駛時間、行駛速度等。有些司機更愿意選擇開車距離最短來達到省油的目的,有些司機為了趕時間而更愿意選擇出行時間最短的路徑。因為現(xiàn)在人們工作生活都很忙,尤其是住在大城市的人們,時間就是金錢,搜索最短時間到達的路徑具有較大應用價值,所以本文主要探討出行時間最短的路徑規(guī)劃。如果把城市交通網(wǎng)看作網(wǎng)絡圖,那么搜索兩個地點之間的最短路徑問題就是網(wǎng)絡圖中節(jié)點之間的最短路徑問題。幾十年來國內(nèi)外科學家提出了多種最短路徑的求解方法,主要有Dijkstra算法、福特算法、福勞特算法等。其中Dijkstra算法是目前已知的理論上最完善的算法。在該算法中,節(jié)點間的連接信息由鄰接矩陣來記錄。在進行最短路徑搜索時以鄰接矩陣為基礎不斷進行目標的最小值判斷,直到獲得最短路徑。但是這些經(jīng)典的算法只能解決兩點間的路程最短問題,而兩點間的路程最短并不代表出行時間最短?，F(xiàn)實生活中很多道路比較擁堵,有時候路程長的路徑反而消耗時間短;如果該路徑交叉口很多,那么車輛通過交叉口帶來的延誤時間是不能忽略的。即使搜索出來的是最短路程的路徑,也無法以最短的時間到達目的地。而且現(xiàn)在有些路段是單行線,所以地圖軟件搜索到的最短路徑有可能是不實用的?；谏鲜隹紤],本文把這3個因素結(jié)合在Dijkstra算法中,提出一種新的改進的Dijkstra算法來解決最短時間到達路徑問題。經(jīng)過算法的編程實現(xiàn),能搜索到一條消耗時間最短的路徑,比較貼近實際情況,能基本滿足用戶需求。1影響最短路徑規(guī)劃的交通因素分析1.1交通擁堵的定量描述從定性的角度看,交通擁堵是交通運行故障的直觀表現(xiàn)形式。但是在做最短時間路徑規(guī)劃時,為了使規(guī)劃出來的路徑更貼近實際情況,必須將交通擁堵這一重要因素考慮在內(nèi),并且有一個量化的定義。我國公布的《城市交通管理評價指標體系》中規(guī)定,用城市主干路上機動車的平均行程速度來描述其交通擁堵程度:(1)暢通:城市主干路上機動車的平均行程速度不低于30km/h;(2)輕度擁擠:城市主干路上機動車的平均行程速度低于30km/h,但高于20km/h;(3)擁擠:城市主干路上機動車的平均行程速度不高于20km/h,但高于10km/h;(4)嚴重擁擠:城市主干路上機動車的平均行程速度不高于10km/h。這種交通擁堵的定量描述具有較高的可操作性,可直接用于道路交通擁堵程度的判別。本文需要從交通部門發(fā)布的實時數(shù)據(jù)中直接或估計得到路段上的平均行駛速度,這樣就能根據(jù)路段長度和平均行駛速度得到該路段較為準確的行駛時間。1.2節(jié)點性能參數(shù)通常的路徑優(yōu)化算法把每個節(jié)點看作是抽象的點,節(jié)點是沒有權重的,在算法中不起任何作用。然而在實際的路網(wǎng)中,因為有紅綠燈的存在,車輛通過節(jié)點交叉口時不可避免地要產(chǎn)生時間的延誤,而且交叉口的時間延誤在整個車輛的出行時間中占有較大比重,因此在路徑優(yōu)化算法中必須考慮車輛通過交叉口時產(chǎn)生的延誤時間,即路網(wǎng)中的節(jié)點也是帶有權重的。1.3傳統(tǒng)路徑優(yōu)化算法為了優(yōu)化交通組織,合理分配路網(wǎng)上的交通流,避免擁堵,交通部門經(jīng)常會在某些路段設置單行線,即該路段車輛只能由這一端開往另一端,而不能由另一端開往這一端。而一般的地圖軟件在路徑規(guī)劃中是不考慮單行線的,所以有些規(guī)劃出來的路徑是不可用的,在算法中必須考慮這一交通因素。在傳統(tǒng)的路徑優(yōu)化算法中,如果兩個節(jié)點之間有弧段,那么這兩個節(jié)點是互通的。有了單行線這一限制條件后,必須改進傳統(tǒng)的路徑優(yōu)化算法。2算法的設計基于最短的路徑規(guī)劃2.1節(jié)點之間的約束時間圖1中,V0是起始點,V5是終點,各個路段的行駛時間已標注,圓圈里的數(shù)字是各節(jié)點交叉口的延誤時間,V2和V3之間的路段設為單行線,只能由V3通往V2,不能由V2通往V3,要搜索V0到V5的最優(yōu)路徑。2.2運行結(jié)果分析在傳統(tǒng)的Dijkstra算法中,節(jié)點是不含權重的,是抽象的,在算法中不起任何作用。但是在規(guī)劃路網(wǎng)的最短時間路徑時,交叉口的延誤時間必須考慮在內(nèi),即節(jié)點是含有權重的,因此傳統(tǒng)的Dijkstra算法不能規(guī)劃出最短時間路徑。本文將節(jié)點的權重轉(zhuǎn)化為新增弧段的權重,就有了將節(jié)點權重考慮在內(nèi)的改進的Dijkstra算法。具體操作有兩方面:(1)初始化最短路徑時,先搜索與起始點V0相鄰的節(jié)點,在計算V0到這些相鄰節(jié)點的權值時,加上這些節(jié)點本身的權值,代碼如下:m_d[i]+=dist[i][i]。(2)在更新當前最短路徑及權值時,也把這些節(jié)點的權值加上,m_d[temp]+dist[temp][j]+dist[j][j]。如果某路段是單行線,則改變鄰接矩陣的相應權值,在上述數(shù)學模型中,V2到V3不可達,V3到V2可達,那么在鄰接矩陣中,V2到V3的值設為最大值,V3到V2的值為該路段的行駛時間。算法具體步驟如下:步驟1新建兩個txt文件,分別命名input.txt和output.txt。在input文件中輸入節(jié)點數(shù)和起始節(jié)點,將路網(wǎng)圖中的弧段權值和節(jié)點權值寫成鄰接矩陣也放入input文件中。而output文件則存儲程序代碼運行結(jié)果,即得到的兩點間最優(yōu)路徑和總的到達時間。定義最大權值和最大節(jié)點數(shù),最大權值設為9999。如果弧段權值等于最大權值時,表示路徑不可達。單行線的表現(xiàn)方式就是如此。步驟2用fopen()函數(shù)打開input文件,讀取節(jié)點數(shù)和最初頂點,讀取各弧段權值和節(jié)點權值。步驟3初始化各路徑頂點圖,路徑矩陣path如下:pathV0V1V2V3V4V5V0000000V1999999999999999999999999V2999999999999999999999999V3999999999999999999999999V4999999999999999999999999V5999999999999999999999999pathV0V1V2V3V4V5V0099999999999999999999V1099999999999999999999V2099999999999999999999V3099999999999999999999V4099999999999999999999V5099999999999999999999步驟4初始化最短路徑,找到與起始點V0相連的節(jié)點,只有V1和V2,路徑矩陣path如下:pathV0V1V2V3V4V5V0000000V1012999999999999V2999999999999999999999999V3999999999999999999999999V4999999999999999999999999V5999999999999999999999999pathV0V1V2V3V4V5V0009999999999999999V1019999999999999999V2029999999999999999V3099999999999999999999V4099999999999999999999V5099999999999999999999步驟5將起始節(jié)點V0加入S集,找到與起始點相連的有路徑的節(jié)點,在圖1中只有V1和V2兩個節(jié)點,并分別計算V0到這兩個節(jié)點的距離,包括節(jié)點權重(延誤時間),比較兩者的大小,將路徑權值小的連接節(jié)點加入S集,即節(jié)點V2。然后從V0ue84dWingdings`C@V2這條路徑出發(fā),尋找與該路徑相鄰的節(jié)點,發(fā)現(xiàn)只有V1和V4兩個節(jié)點。計算V0ue84dWingdings`C@V2ue84dWingdings`C@V1和V0ue84dWingdings`C@V2ue84dWingdings`C@V4的權值,發(fā)現(xiàn)V0ue84dWingdings`C@V2ue84dWingdings`C@V1的權值不小于V0ue84dWingdings`C@V2ue84dWingdings`C@V4的權值,所以舍棄V0ue84dWingdings`C@V2ue84dWingdings`C@V1這條路徑及其權值,保留V0ue84dWingdings`C@V2ue84dWingdings`C@V4這條路徑及其權值。更新最短路徑矩陣path如下:pathV0V1V2V3V4V5V0000000V1012999929999V2999999999999999949999V3999999999999999999999999V4999999999999999999999999V5999999999999999999999999pathV0V1V2V3V4V5V0009999999999999999V1019999999999999999V2029999999999999999V3099999999999999999999V4024999999999999V5099999999999999999999步驟6考察剩余沒有加入S集的節(jié)點,即V1、V3、V4、V5。因為只有V1是起始點V0的鄰接節(jié)點,所以不用比較,將V1加入S集。考察與V1相鄰且沒有放入S集的節(jié)點,只有V3。更新最短路徑矩陣及權值。步驟7不斷執(zhí)行上述步驟5和6,最后得到最短路徑矩陣path為:pathV0V1V2V3V4V5V0000000V1012122V2999999999999344V3999999999999999999995V4999999999999999999999999V5999999999999999999999999pathV0V1V2V3V4V5V0009999999999999999V1019999999999999999V2029999999999999999V3013999999999999V4024999999999999V50245999999992.3e-que大路徑法根據(jù)上述算法,編制改進的Dijkstra算法程序代碼,在VisualStudio2005平臺運行該程序代碼得到V0到V5的最短路徑為V0ue84dWingdings`C@V2ue84dWingdings`C@V4ue84dWingdings`C@V5,計算權值為17。如果路網(wǎng)中沒有考慮交叉口紅綠燈延誤時間和單行線問題,那么最短路徑為V0ue84dWingdings`C@V2ue84dWingdings`C@V3ue84dWingdings`C@V5,權值為9。如果考慮了交叉口紅綠燈延誤時間,不考慮單行線問題,那么最短路徑為V0ue84dWingdings`C@V2ue84dWingdings`C@V3ue84dWingdings`C@V5,權值為15。如果考慮單行線問題,不考慮交叉口紅綠燈延誤時間,那么最短路徑為V0ue84dWingdings`C@V2ue84dWingdings`C@V4ue84dWingdings`C@V5,權值為12。圖1只是一個簡單的小型路網(wǎng),而現(xiàn)實生活中的大型路網(wǎng)利用此算法也能較為精確地規(guī)劃出最短時間路徑,并且計算出出行時間。圖2是某城市中心的交通路網(wǎng)圖。圓圈里的數(shù)據(jù)是節(jié)點編號。根據(jù)實時交通數(shù)據(jù),包括路段長度、各路段擁堵情況、交叉口延誤時間和某些單行線路段,編寫以行駛時間為單位的鄰接矩陣,可以搜索到任何兩節(jié)點間的最短時間路徑及其最短時間。例如:用戶想從地點1到達地點28,如果不考慮交叉口延誤時間和某些路段的單行線,只考慮道路擁堵情況,則用傳統(tǒng)的Dijkstra算法搜索出來的最短時間到達路徑是1ue84dWingdings`C@2ue84dWingdings`C@3ue84dWingdings`C@12ue84dWingdings`C@13ue84dWingdings`C@14ue84dWingdings`C@24ue84dWingdings`C@25ue84dWingdings`C@15ue84dWingdings`C@16ue84dWingdings`C@17ue84dWingdings`C@27ue84dWingdings`C@28;如果考慮道路擁堵情況和交叉口延誤時間,不考慮單行線,則通過改進的Dijkstra算法搜索出來的最短時間到達路徑是1ue84dWingdings`C@10ue84dWingdings`C@11ue84dWingdings`C@12ue84dWingdings`C@3ue84dWingdings`C@4ue84dWingdings`C@5ue84dWingdings`C@14ue84dWingdings`C@15ue84dWingdings`C@25ue84dWingdings`C@26ue84dWingdings`C@27ue84dWingdings`C@28;三者因素都考慮時,最優(yōu)路徑為1ue84dWingdings`C@10ue84dWingdings`C@11ue84dWingdings`C@12ue84dWingdings`C@3ue84dWingdings`C@4ue84dWingdings`C@5ue84dWingdings`C@6ue84dWingdings`C@15ue84dWingdings`C@25ue84dWingdings`C@26ue84dWingdings`C@27ue84dWingdings`C@28,較為貼近現(xiàn)實情況,可以作為出行前考慮的最優(yōu)路徑。2.4調(diào)整節(jié)點的權重本文用平均行駛速度來描述道路擁堵程度,權重的單位就由路段長度變成了行駛時間,由此轉(zhuǎn)化成了一般的網(wǎng)絡求