最短路徑算法分析與應(yīng)用——城市公交網(wǎng)絡(luò)咨詢系統(tǒng).pdf

1、目前在GIS領(lǐng)域,對(duì)最短路徑搜索問題的研究和應(yīng)用較多,其中最短路徑搜索算法的效率問題是普遍關(guān)注和在實(shí)際應(yīng)用中迫切需要解決的問題,圖論中的節(jié)點(diǎn)間求解的最短路徑問題旨在尋找兩個(gè)結(jié)點(diǎn)問的最短路徑。 本文通過對(duì)常見的幾個(gè)有關(guān)最短路徑算法的分析,即經(jīng)典的Dijkstra算法、Bellman-Ford算法、Floyd算法等。討論了各個(gè)算法的思想、實(shí)現(xiàn)方法、數(shù)據(jù)結(jié)構(gòu)及算法描述,并從時(shí)間和空間的復(fù)雜度進(jìn)行分析比較其優(yōu)缺點(diǎn)和具體的實(shí)用性。針對(duì)交通

2、網(wǎng)絡(luò)本身的特點(diǎn)的分析與研究,介紹了一些適合道路網(wǎng)絡(luò)的經(jīng)典最短路徑算法和數(shù)據(jù)存儲(chǔ)模式,探討了在交通網(wǎng)絡(luò)路線優(yōu)化過程中需要特別處理的幾個(gè)問題,并在理論上給出了相應(yīng)的解決方案。 最后特別針對(duì)現(xiàn)代城市交通現(xiàn)狀,目前面臨著的問題,即城市私家車的增加和城市交通運(yùn)輸?shù)陌l(fā)展,造成交通擁擠、道路阻塞和交通事故正越來越突出等諸多,所以積極發(fā)展公交事業(yè)尤為重要。而考慮乘客乘車出行實(shí)際心理,即盡量縮短時(shí)間、縮短路程和縮小費(fèi)用,最終歸結(jié)為圖論中最短路徑問