基于Dijkstra算法優(yōu)化的城市交通路徑分析

吳紅波，王英杰，楊肖肖

(1. 陜西理工大學(xué) 地理科學(xué)系，陜西 漢中 723000；2. 西北大學(xué) 陜西省地表系統(tǒng)與環(huán)境承載力重點(diǎn)實(shí)驗(yàn)室，西安 710127；3. 北京交通大學(xué) 土木建筑工程學(xué)院，北京 100044)

路徑分析是城市交通網(wǎng)絡(luò)分析的研究?jī)?nèi)容之一，也是地理信息系統(tǒng)(Geographic Information System，GIS)空間分析功能的組成部分，并在城市道路管理、網(wǎng)絡(luò)通信、交通規(guī)劃等方面得到廣泛應(yīng)用[1].路徑分析的核心是最短路徑、最佳路徑的求解，而路徑優(yōu)化是利用運(yùn)籌學(xué)規(guī)劃模型使道路網(wǎng)絡(luò)使用、車輛調(diào)度、貨物配送等的運(yùn)行效率達(dá)到最優(yōu).

地理信息系統(tǒng)是將關(guān)系數(shù)據(jù)庫管理、圖形算法、空間插值、區(qū)劃和網(wǎng)絡(luò)分析等功能集成于一體，能有效管理地理空間數(shù)據(jù)，其空間分析可為智慧交通建設(shè)提供技術(shù)支持.近年來，隨著網(wǎng)絡(luò)信息、物聯(lián)網(wǎng)和移動(dòng)互聯(lián)技術(shù)的日益發(fā)展，GIS技術(shù)被應(yīng)用于物流配送、交通規(guī)劃、道路選址、路徑優(yōu)化研究[2]，使得海量地理信息的提取、表現(xiàn)和傳輸任務(wù)變得簡(jiǎn)單易行.在現(xiàn)實(shí)中，最短路徑指的是帶權(quán)圖上的最短路徑問題，不僅是歐氏空間中的距離最短，也可以是時(shí)間最短、費(fèi)用最少、線路使用率最優(yōu)[3].Papinski等[4]考慮距離、行程時(shí)間、速度統(tǒng)計(jì)、交叉口數(shù)、匝數(shù)、停車標(biāo)志/停車燈數(shù)量和路線迂回等變量，借助GIS路徑分析工具箱，對(duì)比分析時(shí)間最短和距離最短的優(yōu)化時(shí)間.Yang等[5]基于GIS網(wǎng)絡(luò)分析工具模塊,對(duì)車輛規(guī)劃路線和固定路線的運(yùn)輸服務(wù)范圍、運(yùn)營(yíng)成本、成本效益進(jìn)行綜合分析.Huang[6]利用GIS網(wǎng)絡(luò)分析和層次分析法(Analytic Hierarchy Process，AHP),分析了道路網(wǎng)絡(luò)中的每個(gè)鏈路的影響因素，結(jié)合危險(xiǎn)品運(yùn)輸車的安全性和運(yùn)輸成本，通過成本函數(shù)模型,量化出每個(gè)運(yùn)輸路線的適用性.針對(duì)小學(xué)生從學(xué)校到家庭住處的行走路線，Duncan等[7-8]聯(lián)合GPS(Global Positioning System)和GIS技術(shù),分析了選線過程中行駛距離、道路節(jié)點(diǎn)、道路擁堵的影響，幫助人們快速確定最短路徑.關(guān)于最短路徑分析算法研究已有較多報(bào)道[9-10]，Bellman算法、Dijkstra算法、Dreyfus算法已成為確定情況下的經(jīng)典算法.而不確定情況下的最短路徑問題，大致分為4個(gè)方面[11]：研究路段長(zhǎng)度隨機(jī)變化的最短路徑；研究不同費(fèi)用函數(shù)的最短路徑；研究時(shí)間獨(dú)立情況下的路段長(zhǎng)度隨機(jī)變化的最短路徑；研究路段長(zhǎng)度為區(qū)間范圍的最短路徑.但以上最短路徑分析未考慮城市車輛在實(shí)際行駛中對(duì)道路選線的不確定因素，為此本文作者在傳統(tǒng)Dijkstra算法優(yōu)化基礎(chǔ)上做進(jìn)一步研究:首先，借助GIS網(wǎng)絡(luò)分析技術(shù),將城市道路網(wǎng)絡(luò)轉(zhuǎn)換成有向圖，包含節(jié)點(diǎn)和鏈路；其次，將城市道路網(wǎng)絡(luò)節(jié)點(diǎn)和路段上距離或時(shí)間阻強(qiáng)(障礙、限速、節(jié)點(diǎn)延遲)作為約束條件；再次，考慮道路類型、節(jié)點(diǎn)停留時(shí)間、限速、車輛行駛方向等條件，對(duì)比分析從起點(diǎn)到終點(diǎn)的時(shí)間或費(fèi)用；最后，根據(jù)時(shí)間成本和距離成本約束因素，分別對(duì)無約束條件、障礙路況、限速模式下的最短路線進(jìn)行了實(shí)地驗(yàn)證，并確定最優(yōu)路線.

1 路徑分析模型

1.1 Dijkstra算法

Dijkstra算法是1959年由荷蘭計(jì)算機(jī)科學(xué)家Dijkstra提出的圖論中求最短路徑的常用算法[12]，該算法可求得圖中一點(diǎn)到其他任一頂點(diǎn)的最短路徑[13].Dijkstra算法將網(wǎng)絡(luò)節(jié)點(diǎn)分成3部分：未標(biāo)記節(jié)點(diǎn)、臨時(shí)標(biāo)記節(jié)點(diǎn)和永久標(biāo)記節(jié)點(diǎn).在網(wǎng)絡(luò)圖中，將所有節(jié)點(diǎn)初始化為未標(biāo)記節(jié)點(diǎn)，在搜索過程中游歷節(jié)點(diǎn)和任一路徑中相連通的節(jié)點(diǎn)為臨時(shí)標(biāo)記節(jié)點(diǎn)，每次循環(huán)都是把從臨時(shí)標(biāo)記節(jié)點(diǎn)中搜索距起源點(diǎn)路徑長(zhǎng)度最短的節(jié)點(diǎn)作為永久標(biāo)記節(jié)點(diǎn)，直至找到目標(biāo)節(jié)點(diǎn)或者所有的節(jié)點(diǎn)都成為永久標(biāo)記節(jié)點(diǎn)后才算法結(jié)束.如圖1所示，假設(shè)節(jié)點(diǎn)網(wǎng)絡(luò)的起源點(diǎn)為節(jié)點(diǎn)0，目標(biāo)點(diǎn)為節(jié)點(diǎn)4，求節(jié)點(diǎn)0到節(jié)點(diǎn)4最短路徑的距離(各節(jié)點(diǎn)間的長(zhǎng)度是假設(shè)的).

圖1 路徑的節(jié)點(diǎn)網(wǎng)絡(luò)Fig.1 The meshed network of the route

假設(shè)每個(gè)節(jié)點(diǎn)都有一對(duì)標(biāo)號(hào)(wi，pj)，wi是起源點(diǎn)到目標(biāo)點(diǎn)的最短路徑的長(zhǎng)度，wj是從起源點(diǎn)s到任意節(jié)點(diǎn)j的最短路徑長(zhǎng)度(從頂點(diǎn)到其本身的最短路徑是零路(沒有弧的路)，其長(zhǎng)度等于零),pj為從起源點(diǎn)s到節(jié)點(diǎn)j的最短路徑中j點(diǎn)的前一節(jié)點(diǎn).求解從起源點(diǎn)i到目標(biāo)節(jié)點(diǎn)j的最短路徑，基本過程如下：

1)初始化.起源點(diǎn)設(shè)置為

①若起源點(diǎn)s最短路徑長(zhǎng)度ws=0，ps為空；

②所有其他節(jié)點(diǎn)的路徑長(zhǎng)度wi=，pi=s；

③標(biāo)記起源點(diǎn)s.記所有已標(biāo)記的節(jié)點(diǎn)k=s，其他節(jié)點(diǎn)設(shè)為未標(biāo)記的.

2)檢驗(yàn)從所有已標(biāo)記的節(jié)點(diǎn)k到其直接連接的未標(biāo)記節(jié)點(diǎn)j的距離，并設(shè)置

wj=min{wj，wk+dkj}

(1)

式中：wj是未標(biāo)記節(jié)點(diǎn)j的最短路徑長(zhǎng)度；wk是已標(biāo)記節(jié)點(diǎn)k的最短路徑長(zhǎng)度；dkj是從節(jié)點(diǎn)k到節(jié)點(diǎn)j的直接連接距離.

3)選取下一個(gè)點(diǎn).從所有未標(biāo)記的節(jié)點(diǎn)wj中，選取最小的一個(gè)標(biāo)記節(jié)點(diǎn)i,即wi=minwj(所有未標(biāo)記的節(jié)點(diǎn)j)，節(jié)點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的點(diǎn).

4)找到節(jié)點(diǎn)i的前一點(diǎn).從已標(biāo)記的節(jié)點(diǎn)中找到直接連接到節(jié)點(diǎn)i的點(diǎn)j′，作為前一點(diǎn)，設(shè)置i=j′.

5)標(biāo)記點(diǎn)i.如果所有節(jié)點(diǎn)已標(biāo)記，則算法求出最短路徑(見表1);否則，記k=i，轉(zhuǎn)到步驟2)再繼續(xù).

表1 0節(jié)點(diǎn)到4節(jié)點(diǎn)的最短路徑

1.2 算法優(yōu)化

Dijkstra算法優(yōu)化思路如下：首先,從起源點(diǎn)s的臨時(shí)集合NBs(與起源點(diǎn)s直接相連的節(jié)點(diǎn)集合)中選擇距離最小的鄰居節(jié)點(diǎn)k作為轉(zhuǎn)接點(diǎn)，同時(shí)劃歸到標(biāo)識(shí)集合S(初始時(shí)，為S{s})；然后，對(duì)k臨時(shí)集合與標(biāo)識(shí)集合的差集中節(jié)點(diǎn)的值進(jìn)行更新，從標(biāo)識(shí)集合S中所有節(jié)點(diǎn)的臨時(shí)集合的并集與標(biāo)識(shí)集合的差集(∪NBsS，i∈S)中選擇一個(gè)路徑距離值最小的節(jié)點(diǎn)Wk作為下一個(gè)轉(zhuǎn)接點(diǎn)，并劃歸到標(biāo)識(shí)集合S中.重復(fù)上述過程，直到所有的節(jié)點(diǎn)都被標(biāo)識(shí)過，即|s|=n，算法結(jié)束.

設(shè)NBi為節(jié)點(diǎn)i的臨時(shí)集合,S為標(biāo)識(shí)集合,wi是從源點(diǎn)s到節(jié)點(diǎn)j的最短路徑長(zhǎng)度,Pi是從s到j(luò)的最短路徑中j點(diǎn)的前一節(jié)點(diǎn),dij是節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離.算法過程[14]如下:

1)初始化標(biāo)識(shí)集合S={s},wi=dsi(i∈NBs),否則wi=(i?NBs)；Pi=s.

2)若k臨時(shí)集合節(jié)點(diǎn)到起源點(diǎn)距離最小dsk=mindsi，則S=S∪{k}，j∈NBs.

3)修改k臨時(shí)集合節(jié)點(diǎn)NBk=S中的wi值,wi=min{wi，wk+dki}；若wi值改變，則Pj=k，j∈NBs-S.

4)選定已標(biāo)記的臨時(shí)節(jié)點(diǎn)集合NBi-S(i∈S)中的wi最小值，并將其劃歸到s中,wk=minwi,S=S∪{k}；若|s|=n,節(jié)點(diǎn)已標(biāo)識(shí)，則算法終止，否則轉(zhuǎn)到步驟3).

對(duì)于節(jié)點(diǎn)總數(shù)為n的網(wǎng)絡(luò)圖，Dijkstra算法求解最短路徑總共需要迭代n-1次，每次迭代都新加一個(gè)節(jié)點(diǎn)到臨時(shí)節(jié)點(diǎn)集合中，由于第i次迭代時(shí)不在臨時(shí)節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)為n-i.那么，第i次迭代需對(duì)n-i個(gè)節(jié)點(diǎn)進(jìn)行處理的次數(shù)為

(2)

當(dāng)式(2)中的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量為n時(shí)，路徑求解的時(shí)間復(fù)雜度為O(n2)，即為網(wǎng)絡(luò)圖上從起源點(diǎn)到其余各節(jié)點(diǎn)的最短路徑求解的時(shí)間復(fù)雜度.隨著節(jié)點(diǎn)總數(shù)n的增大，其計(jì)算效率和存儲(chǔ)效率降低.

時(shí)間復(fù)雜度O(n2)取決于轉(zhuǎn)接點(diǎn)k的臨時(shí)集合NBs的元素?cái)?shù)量，那么優(yōu)化算法空間復(fù)雜度為O(n×p)，其中p為鄰接矩陣存儲(chǔ)結(jié)構(gòu)N×N下節(jié)點(diǎn)對(duì)象所占用的空間，是常量.另外，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)和路段的個(gè)數(shù)，可以求出節(jié)點(diǎn)的平均出度e,即

(3)

式中：m為路段數(shù).

一般在GIS網(wǎng)絡(luò)關(guān)系圖中，e∈[1，4]，由于步驟3)、步驟4)都是搜索與Vi(i=l，2，3，…，n)相鄰的節(jié)點(diǎn)操作，時(shí)間復(fù)雜度均為O(n×e)；步驟4)的時(shí)間復(fù)雜度為O(m)，即O(n×e).

1.3 模型構(gòu)建

選取漢中市主城區(qū)道路網(wǎng)絡(luò)作為研究數(shù)據(jù)，將高速公路、國(guó)道、省道、縣道、鐵路、主干道、次干道、鄉(xiāng)鎮(zhèn)道路等矢量要素導(dǎo)入到本地地理數(shù)據(jù)庫.首先，指定參與道路網(wǎng)絡(luò)矢量要素的拓?fù)涞燃?jí),設(shè)置容限值(限速、限行)和轉(zhuǎn)彎模型，建立道路弧線段-節(jié)點(diǎn)拓?fù)渚W(wǎng)絡(luò)模型；其次，根據(jù)道路網(wǎng)絡(luò)節(jié)點(diǎn)-弧線段連通規(guī)則，設(shè)定費(fèi)用變量和約束變量，費(fèi)用變量為路徑成本費(fèi)用[15]，約束變量屬性字段為布爾值，即為單行和雙行線；最后，設(shè)定道路網(wǎng)絡(luò)中路段的行駛方向和節(jié)點(diǎn)延遲.通過網(wǎng)絡(luò)拓?fù)湟?guī)則和關(guān)系，建立節(jié)點(diǎn)和路段連接的有向網(wǎng)絡(luò)圖，其模型為

(4)

式中：Rw代表道路網(wǎng)絡(luò)；N代表節(jié)點(diǎn)集；R代表路段集合，其元素為有序?qū)Α磝,y〉，且表示由節(jié)點(diǎn)x到節(jié)點(diǎn)y存在一條有向通路；LR代表路段的加權(quán)長(zhǎng)度，其元素L(x,y)表示有向路段〈x,y〉的加權(quán)長(zhǎng)度；lxy為節(jié)點(diǎn)x到節(jié)點(diǎn)y的任一路段長(zhǎng)度.

路段的加權(quán)長(zhǎng)度LR是指根據(jù)多目標(biāo)函數(shù)和規(guī)劃要求，綜合各種動(dòng)態(tài)和靜態(tài)屬性約束條件后求解的最優(yōu)路徑[16]，而并非路徑的實(shí)際距離或者長(zhǎng)度.因此，最優(yōu)路徑不僅指一般地理空間意義上的距離最短[17]，還可以引申到時(shí)間、費(fèi)用、線路容量等[18].

1.4 阻強(qiáng)問題

道路網(wǎng)絡(luò)既有起點(diǎn)、終點(diǎn)、?？奎c(diǎn)、路徑、路障等，又有費(fèi)用成本、等級(jí)、限制和描述符[19].其中，阻強(qiáng)是網(wǎng)絡(luò)中的節(jié)點(diǎn)或路段因某些突發(fā)事件(如交通事故)而不可運(yùn)行時(shí)，原來獲得的最優(yōu)路徑需要進(jìn)行修正，具體步驟如下：

1)修路時(shí)，即某個(gè)路段不可運(yùn)行，屬于永久性的.當(dāng)?shù)缆吩诰S修時(shí)，最優(yōu)路徑的距離也隨著維修狀態(tài)而發(fā)生改變.

2)交叉路口出現(xiàn)車禍等情況時(shí)，暫時(shí)不可通行，即網(wǎng)絡(luò)中的節(jié)點(diǎn)不可運(yùn)行，延長(zhǎng)了車輛行駛時(shí)間.

任一路徑的綜合路阻C采用加權(quán)求和法計(jì)算[20]，有

(5)

式中：Ci為第i路段的綜合路阻；Dij為第i路段中的路阻因素分值；aj為第j路阻因素權(quán)重.

任一路段路阻因素分值Dij的計(jì)算采用上限測(cè)度，計(jì)算公式為

Dij=dij/dj，max

(6)

式中：Dij為第i路段j路阻因素分值；dij為路阻因素的實(shí)際值；dj，max為第j路阻因素的最大實(shí)際值.

2 結(jié)果與討論

2.1 無約束條件下的最優(yōu)路徑

假設(shè)漢中站為初始源點(diǎn)，陜西理工大學(xué)南校區(qū)南門為目標(biāo)節(jié)點(diǎn)，在任意路口可以調(diào)頭，計(jì)算漢中站—陜西理工大學(xué)南校區(qū)南門的距離和時(shí)間最優(yōu)路徑.如圖2(a)所示，在車輛行駛速度理想的狀態(tài)下，從漢中站到陜西理工大學(xué)南校區(qū)南門的距離最短路線長(zhǎng)為4 377.8 m，所用時(shí)間成本為10.7 min，而在時(shí)間約束模式下的路線距離為4 384.9 m，行駛時(shí)長(zhǎng)最小為9.7 min，如圖2(b)所示.在實(shí)際行駛中，路線選擇受駕駛員對(duì)時(shí)間最短和距離最短的偏好影響.

(a)距離最短路徑

(b)時(shí)間最短路徑圖2 路徑選擇Fig.2 Route choice

2.2 障礙路況下的最優(yōu)路徑

假設(shè)在繁雜路口、事故現(xiàn)場(chǎng)、醫(yī)院等位置節(jié)點(diǎn)車流量大，設(shè)置臨時(shí)障礙點(diǎn)，短時(shí)間內(nèi)車輛禁止通過，計(jì)算距離最短和時(shí)間最短路徑.如圖3所示，在障礙路況下，車輛行駛的最短距離為4 610.3 m，時(shí)間成本為10.7 min;最短行駛時(shí)間為10.2 min，行駛距離為4 630.6 m，二者在時(shí)間和距離成本上相差不大.這表明,從漢中站到陜西理工大學(xué)南校區(qū)南門時(shí)，最優(yōu)路徑的選擇受行駛距離或行駛時(shí)間成本的影響甚微，不起決定性作用，可在時(shí)間成本和距離成本模式下自主選擇.

(a)距離最短路徑

(b)時(shí)間最短路徑圖3 障礙路況下路徑選擇Fig.3 Route choice under the barrier

2.3 限速限行模式下的最優(yōu)路徑

基于道路網(wǎng)絡(luò)等級(jí)、路段限速模式下，駕駛員在主觀意愿上會(huì)優(yōu)先選擇省道、國(guó)道、城市主干道，其次選擇城市次干道、鄉(xiāng)鎮(zhèn)道路.假設(shè)主干道限速30 km/h、次干道限速25 km/h、省道限速35 km/h，計(jì)算出在限速模式下的最優(yōu)路徑.在限速模式下，距離最短路徑需要行駛4 455.3 m，行駛時(shí)間成本為13.2 min(見圖4(a))，比無約束模式下的時(shí)間最短路徑多行駛2.3 min.限速模式下的最短時(shí)間為10.5 min，行駛距離為4 739.4 m(見圖4(b))，與最短距離路徑模式相比，時(shí)間成本降低了，距離成本增加了361.5 m.在道路通行能力有限情況下，尤其在上下班高峰期，實(shí)際的行駛時(shí)間與最優(yōu)路徑的行駛時(shí)間存在較大差異.而交通路況在非高峰時(shí)段，最優(yōu)路徑與實(shí)際行駛時(shí)間和距離成本較為接近.

(a)距離最短路徑

(b)時(shí)間最短路徑圖4 限速模式下路徑選擇Fig.4 Route choice under the speed binit mode

優(yōu)化后的Dijkstra算法和傳統(tǒng)Dijkstra算法，在計(jì)算路徑的運(yùn)行時(shí)間和距離最短時(shí)，主要取決于行駛路線的節(jié)點(diǎn)數(shù)量.時(shí)間最短和距離最短路徑的求解有不同之處，主要表現(xiàn)在有向圖中每條路段上障礙點(diǎn)、行駛方向、限速的設(shè)置.假設(shè)每個(gè)限速路段節(jié)點(diǎn)的延時(shí)時(shí)間為30 s，非限速路段的節(jié)點(diǎn)處延時(shí)25 s，行駛過程中通過的紅綠燈最少，計(jì)算出時(shí)間最短路徑為18.4 min，比限速模式下時(shí)間最短路徑的時(shí)間成本多5.2 min，如圖5所示.

圖5 節(jié)點(diǎn)延時(shí)條件下的距離最短路徑Fig.5 The shortest route of distance under the node delay conditions

2.4 選線結(jié)果對(duì)比

為檢驗(yàn)優(yōu)化路線的行駛理論時(shí)長(zhǎng)和實(shí)際行駛時(shí)長(zhǎng)(見表2)，與優(yōu)化路線的行駛時(shí)長(zhǎng)相比，實(shí)際行駛時(shí)間用時(shí)較長(zhǎng)，最小時(shí)長(zhǎng)差值為1.2 min，最大時(shí)長(zhǎng)差值2.9 min.在城市道路網(wǎng)絡(luò)不限速、不限等級(jí)的情況下，時(shí)間最短路徑的行駛距離(線2)比距離最短路徑的行駛距離(線1)多行駛了7.4 m，以行駛距離增加和道路等級(jí)降低來換取行駛時(shí)長(zhǎng)最小化.在障礙路況模式下，線4時(shí)間行駛時(shí)長(zhǎng)比線3的實(shí)際行駛時(shí)長(zhǎng)多了1.0 min，行駛中的駕駛員對(duì)障礙點(diǎn)和路況不熟悉，實(shí)際行駛時(shí)長(zhǎng)比模型輸出的理論行駛時(shí)長(zhǎng)多用了2.9 min.在限速模式下，線5中城市車輛的行駛時(shí)長(zhǎng)實(shí)際值受限于道路擁堵、通行能力、路況信息等條件，比線6實(shí)際行駛時(shí)長(zhǎng)多了1.2 min，與行駛理論時(shí)長(zhǎng)多了2.3 min.而在路口節(jié)點(diǎn)處延時(shí)30 s的情況下，實(shí)際行駛距離較為合理，實(shí)際行駛時(shí)長(zhǎng)較大.因此，節(jié)點(diǎn)延時(shí)、障礙路況、限速限行是影響城市車輛選線的主要因素，最優(yōu)路徑中節(jié)點(diǎn)數(shù)量對(duì)行駛時(shí)長(zhǎng)和行駛距離起到主導(dǎo)作用.

表2 基于Dijkstra算法優(yōu)化的車輛選線與實(shí)際行駛時(shí)間對(duì)比Tab.2 Comparison of actual driving time and vehicle routing results after the optimization of Dijkstra algorithm

3 結(jié)論

1)通過對(duì)傳統(tǒng)Dijkstra算法的優(yōu)化，利用GIS網(wǎng)絡(luò)分析工具，對(duì)城市車輛選線進(jìn)行求解，獲得了不同約束條件下的時(shí)間和距離最優(yōu)路徑，并給出最短路徑長(zhǎng)度和行駛時(shí)間.在理想情況下，GIS網(wǎng)絡(luò)分析工具能夠精準(zhǔn)模擬復(fù)雜的道路網(wǎng)絡(luò)，使模型中的選線結(jié)果與實(shí)際選線結(jié)果較為一致.

2)Dijkstra算法優(yōu)化可減少路徑分析過程中的節(jié)點(diǎn)訪問時(shí)間，降低時(shí)間復(fù)雜度，縮短已標(biāo)識(shí)節(jié)點(diǎn)外的大量節(jié)點(diǎn)的計(jì)算時(shí)長(zhǎng).但是，最優(yōu)路徑的成本仍取決于路徑節(jié)點(diǎn)數(shù)、路段阻強(qiáng)和限速條件.

3)在道路網(wǎng)絡(luò)中指定起源節(jié)點(diǎn)和目標(biāo)點(diǎn)，分別求出在距離、時(shí)間成本的限制下的最優(yōu)路徑.但是針對(duì)城市公共交通工具的進(jìn)出站、路段限行、道路擁堵等路況條件，需要采用相應(yīng)的路徑優(yōu)化措施.Dijkstra算法優(yōu)化傾向于選擇主干道、無障礙路、次干道，在駕駛員主觀和客觀因素(如司機(jī)態(tài)度、偶然事件、擁堵路段、節(jié)點(diǎn)訪問次序、交通臨時(shí)管制)方面還有待進(jìn)一步研究.