高速公路網(wǎng)中的Ｄｉｊｋｓｔｒａ最短路徑優(yōu)化算法

摘要：當(dāng)高速公路網(wǎng)中出現(xiàn)交通事件時，其拓撲結(jié)構(gòu)發(fā)生了變化，需要搜索新的最短路徑并告知司機。由于信息發(fā)布具有較高的實時性，最短路徑的搜索效率對高速公路信息服務(wù)的效率有重要影響。論文采用Dijkstra算法搜索高速公路網(wǎng)中的最短路徑，并結(jié)合高速公路網(wǎng)的特點，用鏈結(jié)構(gòu)將表示各收費站的點連接起來，簡化了高速公路網(wǎng)的拓撲結(jié)構(gòu)，從而大幅減少Dijkstra算法中的節(jié)點數(shù)。對算法的復(fù)雜度分析表明，這種方法大幅減少了路徑搜索的復(fù)雜度，從而縮短了計算時間，提高了最短路徑搜索效率。