求圖中每對頂點間的所有最短路徑算法的分析與研究.pdf

1、最短路徑算法的研究是計算機科學(xué)研究的熱門話題，它有著廣泛的應(yīng)用領(lǐng)域，比如在交通運輸系統(tǒng)、應(yīng)急救助系統(tǒng)、電子導(dǎo)航系統(tǒng)等研究領(lǐng)域。對最短路徑問題的研究不僅具有重要的理論意義，而且具有重要的實用價值。
　　 目前比較經(jīng)典的最短路徑算法是Dijkstra、Floyd等算法，這些算法求解的是某對頂點間的一條最短路徑和每對頂點間的一條最短路徑。隨著科技的發(fā)展，這類算法已經(jīng)無法解決實際應(yīng)用中出現(xiàn)的很多問題了，比如在應(yīng)急救助系統(tǒng)中心、貨物運輸調(diào)

2、度中心等領(lǐng)域，我們需要的不僅僅是某對頂點間的一條最短路徑，而是全方位的信息，以供調(diào)度中心使用。本文針對這種情況，對最短路徑問題進行了分析研究，提出了求圖中每對頂點間的所有最短路徑問題，同時提出了帶限制條件的每對頂點間的所有最短路徑問題。解決此類問題的算法在貨物運輸系統(tǒng)、應(yīng)急救助系統(tǒng)等領(lǐng)域有著重大的實用價值。
　　 本文首先介紹了最短路徑問題的研究現(xiàn)狀、研究意義等。其次介紹了圖的相關(guān)知識以及常用算法的相關(guān)知識。接著對最短路徑算法進

3、行了分析研究并提出了本文的算法。本文主要內(nèi)容集中在第四章。第四章一共提出了三種相關(guān)算法。
　　 1．提出了求圖中每對頂點間的所有最短路徑的基本算法。該算法基于邊序列，通過逐步加入圖中的每條邊，判斷加入該邊后，圖中每對頂點間的當前最短路徑是否有更新，進行邊松弛操作，記錄圖中每對頂點間的最新最短路徑長度，并保存直接后繼結(jié)點信息，直至所有的邊都處理完。然后根據(jù)直接后繼結(jié)點鏈表遍歷生成每對頂點間的所有最短路徑。該算法的時間復(fù)雜度為max

4、{O(n3*e)，O(n*Shpah(G))}(其中n為圖中的頂點數(shù)，e為圖中的邊數(shù)，Shpath(G)為所生成的最短路徑的數(shù)目總和)。
　　 2．提出了求圖中每對頂點間的所有最短路徑的改進算法。該算法采用逆拓撲順序從出度為0的結(jié)點開始，更新該結(jié)點的逆鄰接點到該結(jié)點，以及到從該結(jié)點出發(fā)有路可通的其他結(jié)點的最短路徑長度，將該結(jié)點的逆鄰接點的出度減1，并記錄直接后繼結(jié)點信息。對所有的出度為0的結(jié)點進行同樣的操作，直至無出度為0的結(jié)點

5、。再根據(jù)直接后繼結(jié)點鏈表，從后往前生成每對頂點間的所有最短路徑。算法的時間復(fù)雜度為max{O(n3)，O(n*allSH(G))}(其中n為圖中的頂點數(shù)，allSH(G)為圖中每對頂點間的所有最短路徑的數(shù)量總和)。
　　 3．提出了求圖中受頂點數(shù)限制的每對頂點間的所有最短路徑的算法。該算法也是采用逆拓撲順序，更新每對頂點間的最短路徑樹結(jié)點信息(包括最短路徑長度以及經(jīng)過的頂點數(shù))，最后根據(jù)最短路徑樹結(jié)點信息遍歷生成受頂點數(shù)限制的每