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

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