范俊怡，劉栩含，龍 玲

（四川省南充高級中學(xué)，四川 南充637000）

1 引言

信息學(xué)競賽考察內(nèi)容廣泛，包含貪心算法、分治算法、動(dòng)態(tài)規(guī)劃以及圖論相關(guān)算法等。其中圖論在計(jì)算機(jī)中扮演著重要的角色，許多問題都需要抽象成圖，然后運(yùn)用圖論的相關(guān)算法來解決。最短路問題是圖論中一個(gè)經(jīng)典問題，曾多次出現(xiàn)在信息學(xué)競賽考場上；同時(shí)最短路也與實(shí)際生活息息相關(guān)，比如常用的地圖導(dǎo)航涉及的路徑規(guī)劃使用的核心算法就是最短路算法，因此競賽生需要牢牢掌握最短路的相關(guān)算法。

2 最短路問題

最短路問題主要是研究在帶權(quán)連通圖中，一個(gè)結(jié)點(diǎn)到達(dá)另一個(gè)結(jié)點(diǎn)的所有路徑中找權(quán)值和最小的一條路徑。所謂帶權(quán)連通圖指圖中任意一條邊是帶有權(quán)值的，并且任意兩結(jié)點(diǎn)之間至少存在一條路徑。

在信息學(xué)競賽中，主要給學(xué)生講解四種常用的求解最短路問題的算法，這四種算法各有優(yōu)劣，對于不同的競賽題目，推薦學(xué)生選擇較優(yōu)的算法解題。

3 最短路算法

3.1 Floyed-Warshall算法

Floyed-Warshall算法又稱弗洛伊德最短路算法，該算法是利用動(dòng)態(tài)規(guī)劃算法的思想求解最短路問題的算法，復(fù)雜度為O（n3）。調(diào)用一次Floyed-Warshall算法就可以直接求出一個(gè)n階圖的任意兩個(gè)結(jié)點(diǎn)之間的最短路，稱之為多源最短路算法。

優(yōu)點(diǎn)：學(xué)生容易理解和記憶，代碼實(shí)現(xiàn)簡單；可以處理存在負(fù)邊權(quán)的圖；有向圖和無向圖都可適用。

缺點(diǎn)：時(shí)間復(fù)雜度高，不適合大數(shù)據(jù)求解；必須用鄰接矩陣存儲(chǔ)數(shù)據(jù)，內(nèi)存占用大，適用于稠密圖。

算法思想：設(shè)一個(gè)圖的信息用鄰接矩陣二維g數(shù)組存儲(chǔ)，如果結(jié)點(diǎn)i和結(jié)點(diǎn)j直接聯(lián)通，g［i］［j］等于i和j的邊權(quán)，如果i和j不連通，則g［i］［j］等于無窮大。

設(shè)dis［i］［j］［k］表示i到j(luò)的路徑上的中間結(jié)點(diǎn)只經(jīng)過1～k時(shí)，i到j(luò)為最短路距離。

最短路經(jīng)過k:dis［i］［j］［k］=dis［i］［k］［k-1］+dis［k］［j］［k-1］。

最短路不經(jīng)過k:dis［i］［j］［k］=dis［i］［j］［k-1］綜上，狀態(tài)轉(zhuǎn)移方程為dis［i］［j］［k］=min(dis［i］［j］［k-1］，dis［i］［k］［k-1］+dis［k］［j］［k-1］)。

分析以上狀態(tài)轉(zhuǎn)移方程不難發(fā)現(xiàn)，在狀態(tài)轉(zhuǎn)移過程中，k的值是不斷遞增的，所以可以進(jìn)行空間優(yōu)化，直接去掉第三個(gè)維度k，用一個(gè)二維數(shù)組dis［i］［j］就可以完成最短路徑的計(jì)算。

邊界條件：dis［i］［j］=g［i］［j］。

核心代碼1如圖1所示。i、j、k三者不要重復(fù)相等。

圖1 核心代碼

Floyed-Warshall算法的變形主要作用是判斷無權(quán)圖中的兩結(jié)點(diǎn)是否連通。

設(shè)鄰接矩陣bool數(shù)組g［i］［j］=true表示i和j直接連通，g［i］［j］=false表示i和j不直接連通。

邊界條件：dis［i］［j］=g［i］［j］。

核心代碼2如圖2所示。

圖2 核心代碼2

3.2 Dijkstra算法

Dijkstra算法又稱迪杰斯特拉算法。該算法是利用貪心算法的思想求解最短路問題的算法，復(fù)雜度為O（n2）。調(diào)用一次Dijkstra算法就可以直接求出一個(gè)已定的結(jié)點(diǎn)到圖中其他所有結(jié)點(diǎn)的最短路徑，稱之為單源最短路算法。

優(yōu)點(diǎn)：算法思路簡明、容易理解；時(shí)間復(fù)雜度低，如果加堆優(yōu)化復(fù)雜度可達(dá)O（n*logn）。

缺點(diǎn)：不能處理存在負(fù)邊權(quán)的圖。

算法思想：設(shè)已知帶權(quán)圖G=(V，E)，其中V是結(jié)點(diǎn)的集合，E是邊的集合，求解v0到其他所有結(jié)點(diǎn)的最短路，用dis［i］表示v0到i的最短路。該算法采用貪心策略，將結(jié)點(diǎn)分到兩個(gè)集合S、U中，S集中的結(jié)點(diǎn)v已經(jīng)求出了最短路dis［v］，并且不再更新值。對于U中的結(jié)點(diǎn)u，dis［u］不一定是v0到u的最短路，還需要進(jìn)一步計(jì)算。計(jì)算的方式是每次從U中選擇一個(gè)dis［u］最小的結(jié)點(diǎn)u，把u加入S中。并用u作為中間結(jié)點(diǎn)，更新U中其他結(jié)點(diǎn)u1的dis［u1］。

算法步驟：①初始化dis［v0］=0，其他dis［i］=+∞。②執(zhí)行n次如下操作，每次確定一個(gè)結(jié)點(diǎn)v的最短路dis［v］。選擇未被標(biāo)記的結(jié)點(diǎn)k并且dis［k］最??；標(biāo)記k，可以用一個(gè)bool數(shù)組vis［k］=true標(biāo)記；以k為中間點(diǎn)，修改其余未被標(biāo)記的點(diǎn)的u的最短路的值dis［u］。核心代碼【版本1】：鄰接矩陣O（n2），如圖3所示。

圖3 核心代碼【版本1】

樸素版Dijkstra算法的時(shí)間復(fù)雜度達(dá)到O（n2）。

核心代碼【版本2】：堆（優(yōu)先隊(duì)列）+鄰接表優(yōu)化O（nlogn），如圖4所示。

圖4 核心代碼【版本2】

3.3 Bellman-Ford算法

Bellmaxn-Ford算法是求解包含負(fù)邊權(quán)的單源最短路問題的一種算法，算法時(shí)間復(fù)雜度為O（nm），因?yàn)镈ijkstra算法不能解決有負(fù)邊權(quán)的最短路，因此Bellman-Ford比Dijkstra算法適用范圍更廣一些。

優(yōu)點(diǎn)：可以處理邊權(quán)為負(fù)值的圖，思路簡潔易掌握。

缺點(diǎn)：時(shí)間復(fù)雜度高，無法處理存在負(fù)權(quán)回路情況。

算法思想：與Dijkstra算法相同，求解v0到其他所有結(jié)點(diǎn)的最短路，用dis［i］表示v0到i的最短路。接下來對所有邊進(jìn)行松弛操作，求出每個(gè)點(diǎn)到v0的最短距離；然后遍歷所有邊的兩個(gè)端點(diǎn)，如果存在從源點(diǎn)可達(dá)的負(fù)環(huán)即dis［u］+g［u］［v］

算法步驟：初始化dis數(shù)組為正無窮，dis［s］=0；進(jìn)行n-1次操作，每一次遍歷所有邊，對于每條邊u-v，如果以u為中介點(diǎn)可以使dis［v］更小，就更新dis［v］；檢驗(yàn)圖中是否存在負(fù)環(huán)，即遍歷所有邊判斷dis［u］+g［u］［v］

Bellman-Ford算法下核心代碼如圖5所示。

圖5 Bellman-Ford算法下核心代碼

3.4 SPFA算法

雖然Bellman-Ford算法思路簡潔，但是時(shí)間復(fù)雜度卻很高，在比賽中不太實(shí)用。仔細(xì)分析可以發(fā)現(xiàn)，在Bellman-Ford算法中，只有當(dāng)起始點(diǎn)u的dis［u］值發(fā)生改變時(shí)，其出邊對應(yīng)的終點(diǎn)v的dis［v］值才可能發(fā)生改變，基于這一點(diǎn)，可以利用隊(duì)列對Bellman-Ford算法進(jìn)行優(yōu)化，優(yōu)化后得到的就是SPFA算法，算法時(shí)間復(fù)雜度為O（km），m為圖的邊數(shù)，k為所有頂點(diǎn)入隊(duì)的平均次數(shù)，在很多情況k是小于等于2的，因此在大多數(shù)時(shí)候SPFA算法性能都很好。

優(yōu)點(diǎn)：時(shí)間復(fù)雜度低，可以處理存在負(fù)邊權(quán)的情況。

缺點(diǎn)：不能處理負(fù)環(huán)。

算法思想：基于Bellman-Ford算法，可以發(fā)現(xiàn)只有當(dāng)某個(gè)點(diǎn)u到源點(diǎn)的最短距離dis［u］發(fā)生改變，才可能影響從u出發(fā)的邊到達(dá)的終點(diǎn)v的dis［v］值。因此，可以建立一個(gè)隊(duì)列，每次取出隊(duì)頭節(jié)點(diǎn)u，然后遍歷u所有的出邊進(jìn)行松弛操作，如果dis［u］+g［u］［v］

算法步驟：初始化dis數(shù)組為正無窮，dis［s］=0，num數(shù)組初始化為0，num［s］=1，將源點(diǎn)s入隊(duì)，將s的入隊(duì)標(biāo)記flag［s］設(shè)為true；當(dāng)隊(duì)列不為空時(shí)，取出隊(duì)頭結(jié)點(diǎn)u，更改u的標(biāo)記為false；遍歷u的所有出邊進(jìn)行松弛操作，如果以u為中介點(diǎn)可以使dis［v］更小，就更新dis［v］，如果v被更新且v不在隊(duì)列中，那么將v入隊(duì)，更改v的入隊(duì)標(biāo)記，同時(shí)num［v］++，如果num［v］>=n，則返回false。SPFA算法下核心代碼如圖6所示。

圖6 SPFA算法下核心代碼

4 最短路算法的選擇

對于不同的競賽題目，學(xué)生可以分析題意，將題目抽象成圖后，根據(jù)圖的性質(zhì)：求單源最短路還是多源最短路、稀疏圖還是稠密圖、是否存在負(fù)權(quán)邊等來選擇對應(yīng)的算法，例如稀疏圖（無論是否存在負(fù)權(quán)邊），建議采用SPFA算法，效率會(huì)更高，而對于稠密圖可以分情況討論，不存在負(fù)權(quán)時(shí)建議使用Dijkstra算法，如果對時(shí)間要求不是太嚴(yán)格，也可以采用Floyd算法；具體問題還需具體分析，以上建議只是一個(gè)參考。最短路問題是許多更深層次圖論問題的基礎(chǔ)，學(xué)好最短路算法，可為后續(xù)學(xué)習(xí)更復(fù)雜的圖論算法做準(zhǔn)備。