最短路徑算法問題
頁數(shù) 31 字?jǐn)?shù) 11419

摘 要
最短路徑算法問題是計算機科學(xué)、運籌學(xué)、地理信息系統(tǒng)和交通誘導(dǎo)、導(dǎo)航系統(tǒng)等領(lǐng)域研究的一個熱點。傳統(tǒng)的最短路徑算法主要有Floyd算法和Dijkstra算法。Floyd算法用于計算所有節(jié)點之間的最短路徑。Dijkstra算法則用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。Dijkstra算法是已經(jīng)證明的能得出最短路徑的最優(yōu)解，但它的效率是一個很大的問題。對于具有n個節(jié)點的一個圖，計算一個節(jié)點到圖中其余節(jié)點最短路徑的算法時間復(fù)雜度為O(n2)。對于一座大中型城市，地理節(jié)點數(shù)目可能達到幾萬個到幾十萬個，計算最短路徑的時間開銷將是非常巨大的。
本文根據(jù)吳一民老師的建議，分析當(dāng)前存在的各種求最短路徑的算法，提出一種新的基于層次圖的最短路徑算法，即將一個平面圖劃分若干子圖，子圖抽象為一個高層圖。最短路徑的計算首先在高層圖中進行，縮小了最短路徑的查找范圍，降低了最短路徑計算的時間開銷。由于可以動態(tài)計算子圖間的阻抗函數(shù)，算法可適用于動態(tài)交通誘導(dǎo)系統(tǒng)。


關(guān)鍵詞 最短路徑，層次圖模型，Dijkstra算法




ABSTRACT
This paper discusses a new algorithm for the shortest path founding based on hierarchical graphs. It plots out a flat graph into some sub-graphs, which are abstracted as a high-level graph. The calculation for the shortest path founding begins at the high-level graph. This method shrinks the searching range of the shortest path and reduces the time spending of calculating it. Since the impedance function among sub-graphs can be calculated dynamically, this algorithm can be applied to dynamic traffic inducement system.

Index Terms: shortest path, hierarchical graph, Dijkstra algorithm