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

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

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