求圖中受頂點(diǎn)數(shù)限制的所有最短路徑的算法分析研究.pdf

1、解決圖中受頂點(diǎn)數(shù)限制的最短路徑問題在交通工程、通信網(wǎng)絡(luò)等方面有重要的實(shí)際意義。本文主要是針對K頂點(diǎn)數(shù)限制最短路徑問題提出求解算法。在實(shí)際應(yīng)用中，除希望得到最短路徑外，還希望得到次短、再次短等路徑，稱為廣義最短路徑，本文還提出了受K頂點(diǎn)數(shù)受限制的廣義最短路徑的求解算法。 本文首先介紹了最短路徑問題的研究意義、現(xiàn)狀等，接著對圖的基本知識和最短路徑問題做了簡單介紹，并對求解最短路徑問題常用算法和本文工作相關(guān)的最短路徑算法作了總結(jié)概述。

2、 第三章是本文的主要工作，本章首先給出了求解圖中受K頂點(diǎn)數(shù)限制的所有最短路徑的一種基礎(chǔ)算法，簡稱BCSP算法，BCSP算法借助了圖的廣度搜索算法，生成擴(kuò)展最短路徑樹，然后根據(jù)擴(kuò)展最短路徑樹輸出所有最短路徑；算法的時間復(fù)雜度為(n為圖中頂點(diǎn)總數(shù)，k為受限制的頂點(diǎn)數(shù)，c為相應(yīng)生成樹中每一層結(jié)點(diǎn)數(shù)。為了提高算法效率，本文又提出了新的改進(jìn)算法，簡稱ICSP算法，ICSP算法采用了逆鄰接表、標(biāo)記數(shù)組等數(shù)據(jù)結(jié)構(gòu)并靈活使用了指針等，此算法主要

3、是在求解最短路徑的基礎(chǔ)上生成了有效前驅(qū)結(jié)點(diǎn)鏈表而其它相關(guān)算法都只關(guān)注于一個有效前驅(qū)結(jié)點(diǎn)；相對算法BCSP而言，ICSP算法的時間復(fù)雜度得到了很大程度的優(yōu)化，時間復(fù)雜度為max{0((k-2)*w)，0(k*sh(G，j，j))}(w為圖中弧的條數(shù)，sh(G,j，j)為所有受頂點(diǎn)數(shù)限制的最短路徑條數(shù))。在實(shí)際問題中可能還需考慮圖的次短等路徑，因此本文提出了求解受頂點(diǎn)數(shù)限制的廣義最短路徑算法，簡稱GCSF 算法，它在算法ICSP的基礎(chǔ)上采用