詳談Dijkstra算法
本文由單源最短路徑路徑問(wèn)題開(kāi)始，而后描述Bellman-Ford算法，到具體闡述Dijkstra算法，闡述詳細(xì)剖析Dijkstra算法的每一個(gè)步驟，教你徹底理解此Dijkstra算法。
一、單源最短路徑問(wèn)題
我們知道，單源最短路徑問(wèn)題：已知圖G=(V，E)，要求找出從某個(gè)定源頂點(diǎn)s<-V，到每個(gè)v<-V的最短路徑。簡(jiǎn)單來(lái)說(shuō)，就是一個(gè)圖G中，找到一個(gè)定點(diǎn)s，然后以s為起點(diǎn)，要求找出s到圖G中其余各個(gè)點(diǎn)的最短距離或路徑。
此單源最短路徑問(wèn)題有以下幾個(gè)變形：
I、 單終點(diǎn)最短路徑問(wèn)題： 每個(gè)頂點(diǎn)v到指定終點(diǎn)t的最短路徑問(wèn)題。即單源最短路徑問(wèn)題的相對(duì)問(wèn)題。
II、 單對(duì)頂點(diǎn)最短路徑問(wèn)題：給定頂點(diǎn)u和v，找出從u到v的一條最短路徑。
III、每對(duì)頂點(diǎn)間最短路徑問(wèn)題：
針對(duì)任意每倆個(gè)頂點(diǎn)u和v，找出從u到v的最短路徑。最簡(jiǎn)單的想法是，將每個(gè)頂點(diǎn)作為源點(diǎn)，運(yùn)行一次單源算法即可以解決這個(gè)問(wèn)題。當(dāng)然，還有更好的辦法。
二、Bellman-Ford 算法
1、回路問(wèn)題
一條最短路徑不能包含負(fù)權(quán)回路，也不能包含正權(quán)回路。一些最短路徑的算法，如Dijkstra 算法，要求圖中所有的邊的權(quán)值都是非負(fù)的，如在公路地圖上，找一條從定點(diǎn)s到目的頂點(diǎn)v的最短路徑問(wèn)題。
2、Bellman-Ford 算法
而B(niǎo)ellman-Ford 算法，則允許輸入圖中存在負(fù)權(quán)邊，只要不存在從源點(diǎn)可達(dá)的負(fù)權(quán)回路，即可。簡(jiǎn)單的說(shuō)，圖中可以存在負(fù)權(quán)邊，但此條負(fù)權(quán)邊，構(gòu)不成負(fù)權(quán)回路，不影響回路的形成。且，Bellman-Ford 算法本身，便是可判斷圖中是否存在從源點(diǎn)可達(dá)的負(fù)權(quán)回路，若存在負(fù)權(quán)回路，算法返回FALSE,若不存在，返回TRUE。
Bellman-Ford 算法的具體描述
BELLMAN-FORD(G, w, s)
- INITIALIZE-SINGLE-SOURCE(G, s) //對(duì)每個(gè)頂點(diǎn)初始化 ，O(V)
- for i ← 1 to |V[G]| - 1
- do for each edge (u, v) ∈ E[G]
- do RELAX(u, v, w) //針對(duì)每個(gè)頂點(diǎn)(V-1個(gè))，都運(yùn)用松弛技術(shù)O(E)，計(jì)為O（(v-1)*E)）
- for each edge (u, v) ∈ E[G]
- do if d[v] > d[u] + w(u, v)
- then return FALSE //檢測(cè)圖中每條邊，判斷是否包含負(fù)權(quán)回路，
- //若d[v]>d[u]+w(u，v)，則表示包含，返回FALSE，
- return TRUE //不包含負(fù)權(quán)回路，返回TRUE
Bellman-Ford 算法的時(shí)間復(fù)雜度，由上可得為O（V*E）。
3、關(guān)于判斷圖中是否包含負(fù)權(quán)回路的問(wèn)題：
根據(jù)定理，我們假定，u是v的父輩，或父母，那么，當(dāng)G(V,E)是一個(gè)有向圖或無(wú)向圖(且不包含任何負(fù)權(quán)回路)，s<-V，s為G的任意一個(gè)頂點(diǎn)，則對(duì)任意邊(u，v)<-V，有
d[s，v] <= d[s，u]+1
此定理的詳細(xì)證明，可參考算法導(dǎo)論一書(shū)上，第22章中引理22.1的證明?；蛘吒鶕?jù)第24章中通過(guò)三角不等式論證Bellman-Ford算法的正確性，也可得出上述定理的變形。
即假設(shè)圖G中不包含負(fù)權(quán)回路，可證得
- d[v]=$(s，u)
- <=$(s，u)+w(u，v) //根據(jù)三角不等式
- =d[u]+w[u，v]
所以，在不包含負(fù)權(quán)回路的圖中，是可以得出d[v]<=d[u]+w(u，v)。
于是，就不難理解，在上述Bellman-Ford 算法中， if d[v] > d[u]+w(u，v)，=> 包含負(fù)權(quán)回路，返回FASLE
else if =>不包含負(fù)權(quán)回路，返回TRUE。
ok，咱們，接下來(lái)，立馬切入Dijkstra 算法。
三、深入淺出，徹底解剖Dijkstra 算法
I、松弛技術(shù)RELAX的介紹
Dijkstra 算法使用了松弛技術(shù)，對(duì)每個(gè)頂點(diǎn)v<-V，都設(shè)置一個(gè)屬性d[v]，用來(lái)描述從源點(diǎn)s到v的最短路徑上權(quán)值的上界，
稱為最短路徑的估計(jì)。
首先，得用O（V）的時(shí)間，來(lái)對(duì)最短路徑的估計(jì)，和對(duì)前驅(qū)進(jìn)行初始化工作。
- INITIALIZE-SINGLE-SOURCE(G, s)
- for each vertex v ∈ V[G]
- do d[v] ← ∞
- π[v] ← NIL //O（V）
- d[s] 0
- RELAX(u, v, w)
- if d[v] > d[u] + w(u, v)
- then d[v] ← d[u] + w(u, v)
- π[v] ← u //O（E）圖。
II、Dijkstra 算法
此Dijkstra 算法分三個(gè)步驟，INSERT (第3行), EXTRACT-MIN (第5行), 和DECREASE-KEY(第8行的RELAX，調(diào)用此減小關(guān)鍵字的操作)。
- DIJKSTRA(G, w, s)
- INITIALIZE-SINGLE-SOURCE(G, s) //對(duì)每個(gè)頂點(diǎn)初始化 ，O(V)
- S ← Ø
- Q ← V[G] //INSERT，O(1)
- while Q ≠ Ø
- do u ← EXTRACT-MIN(Q) //簡(jiǎn)單的O(V*V)；二叉/項(xiàng)堆，和FIB-HEAP的話，則都為O(V*lgV)。
- S ← S ∪{u}
- for each vertex v ∈ Adj[u]
- do RELAX(u, v, w) //簡(jiǎn)單方式:O(E)，二叉/項(xiàng)堆，E*O(lgV)，F(xiàn)IB-HEAP，E*O(1)。
四、Dijkstra 算法的運(yùn)行時(shí)間
在繼續(xù)闡述之前，得先聲明一個(gè)問(wèn)題，DIJKSTRA（G，w，s）算法中的第5行，EXTRACT-MIN(Q)，最小優(yōu)先隊(duì)列的具體實(shí)現(xiàn)。而Dijkstra 算法的運(yùn)行時(shí)間，則與此最小優(yōu)先隊(duì)列的采取何種具體實(shí)現(xiàn)，有關(guān)。
最小優(yōu)先隊(duì)列三種實(shí)現(xiàn)方法：
1、利用從1至|V| 編好號(hào)的頂點(diǎn)，簡(jiǎn)單地將每一個(gè)d[v]存入一個(gè)數(shù)組中對(duì)應(yīng)的第v項(xiàng)，如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的運(yùn)行時(shí)間為O(V^2+E)。
2、如果是二叉/項(xiàng)堆實(shí)現(xiàn)最小優(yōu)先隊(duì)列的話，EXTRACT-MIN(Q)的運(yùn)行時(shí)間為O(V*lgV)，所以，Dijkstra 算法的運(yùn)行時(shí)間為O(V*lgV+E*lgV)，若所有頂點(diǎn)都是從源點(diǎn)可達(dá)的話，O（(V+E)*lgV）=O（E*lgV）。當(dāng)是稀疏圖時(shí)，則E=O(V^2/lgV)，此Dijkstra 算法的運(yùn)行時(shí)間為O(V^2)。
3、采用斐波那契堆實(shí)現(xiàn)最小優(yōu)先隊(duì)列的話，EXTRACT-MIN(Q)的運(yùn)行時(shí)間為O(V*lgV)，所以，此Dijkstra 算法的運(yùn)行時(shí)間即為O(V*lgV+E)。
綜上所述，此最小優(yōu)先隊(duì)列的三種實(shí)現(xiàn)方法比較如下：
當(dāng)|V|<<|E|時(shí)，采用DIJKSTRA（G，w，s）+ FIB-HEAP-EXTRACT-MIN(Q)，即斐波那契堆實(shí)現(xiàn)最小優(yōu)先隊(duì)列的話，
優(yōu)勢(shì)就體現(xiàn)出來(lái)了。
五、Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)，斐波那契堆實(shí)現(xiàn)最小優(yōu)先隊(duì)列
由以上內(nèi)容，我們已經(jīng)知道，用斐波那契堆來(lái)實(shí)現(xiàn)最小優(yōu)先隊(duì)列，可以將運(yùn)行時(shí)間提升到O（VlgV+E）。|V|個(gè)EXTRACT-MIN 操作，每個(gè)平攤代價(jià)為O（lgV），|E|個(gè)DECREASE-KEY操作的每個(gè)平攤時(shí)間為O（1）。
下面，重點(diǎn)闡述DIJKSTRA(G, w, s)中，斐波那契堆實(shí)現(xiàn)最小優(yōu)先隊(duì)列的操作。
由上，我們已經(jīng)知道，DIJKSTRA算法包含以下的三個(gè)步驟：
INSERT (第3行), EXTRACT-MIN (第5行), 和DECREASE-KEY(第8行的RELAX)。
先直接給出Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)的算法：
- DIJKSTRA(G, w, s)
- INITIALIZE-SINGLE-SOURCE(G, s)
- S ← Ø
- Q ← V[G] //第3行，INSERT操作，O（1）
- while Q ≠ Ø
- do u ← EXTRACT-MIN(Q) //第5行，EXTRACT-MIN操作，V*lgV
- S ← S ∪{u}
- for each vertex v ∈ Adj[u]
- do RELAX(u, v, w) //第8行，RELAX操作，E*O(1)
- FIB-HEAP-EXTRACT-MIN(H) //平攤代價(jià)為O（lgV）
- z ← min[H]
- if z ≠ NIL
- then for each child x of z
- do add x to the root list of H
- p[x] ← NIL
- remove z from the root list of H
- if z = right[z]
- then min[H] ← NIL
- else min[H] ← right[z]
- CONSOLIDATE(H)
- n[H] ← n[H] - 1
- return z
六、Dijkstra 算法 +fibonacci堆各項(xiàng)步驟的具體分析
ok，接下來(lái)，具體分步驟闡述以上各個(gè)操作：
第3行的INSERT操作：
- FIB-HEAP-INSERT(H, x) //平攤代價(jià)，O（1）.
- degree[x] ← 0
- p[x] ← NIL
- child[x] ← NIL
- left[x] ← x
- right[x] ← x
- mark[x] ← FALSE
- concatenate the root list containing x with root list H
- if min[H] = NIL or key[x] < key[min[H]]
- then min[H] ← x
- n[H] ← n[H] + 1
第5行的EXTRACT-MIN操作：
- FIB-HEAP-EXTRACT-MIN(H) //平攤代價(jià)為O（lgV）
- z ← min[H]
- if z ≠ NIL
- then for each child x of z
- do add x to the root list of H
- p[x] ← NIL
- remove z from the root list of H
- if z = right[z]
- then min[H] ← NIL
- else min[H] ← right[z]
- CONSOLIDATE(H) //CONSOLIDATE算法在下面，給出。
- n[H] ← n[H] - 1
- return z
下圖是FIB-HEAP-EXTRACT-MIN 的過(guò)程示意圖：
- CONSOLIDATE(H)
- for i ← 0 to D(n[H])
- do A[i] ← NIL
- for each node w in the root list of H
- do x ← w
- d ← degree[x] //子女?dāng)?shù)
- while A[d] ≠ NIL
- do y ← A[d]
- if key[x] > key[y]
- then exchange x <-> y
- FIB-HEAP-LINK(H, y, x) //下面給出。
- A[d] ← NIL
- d ← d + 1
- A[d] ← x
- min[H] ← NIL
- for i ← 0 to D(n[H])
- do if A[i] ≠ NIL
- then add A[i] to the root list of H
- if min[H] = NIL or key[A[i]] < key[min[H]]
- then min[H] ← A[i]
- FIB-HEAP-LINK(H, y, x) //y鏈接至 x。
- remove y from the root list of H
- make y a child of x, incrementing degree[x]
- mark[y] ← FALSE
第8行的RELAX的操作，已上已經(jīng)給出:
- RELAX(u, v, w)
- if d[v] > d[u] + w(u, v)
- then d[v] ← d[u] + w(u, v)
- π[v] ← u //O（E）
一般來(lái)說(shuō)，在Dijkstra 算法中，DECREASE-KEY的調(diào)用次數(shù)遠(yuǎn)多于EXTRACT-MIN的調(diào)用，
所以在不增加EXTRACT-MIN 操作的平攤時(shí)間前提下，盡量減小DECREASE-KEY操作的平攤時(shí)間，都能獲得對(duì)比二叉堆更快的實(shí)現(xiàn)。
以下，是二叉堆，二項(xiàng)堆，斐波那契堆的各項(xiàng)操作的時(shí)間復(fù)雜度的比較：
操作 二叉堆(最壞) 二項(xiàng)堆(最壞) 斐波那契堆(平攤)
MAKE-HEAP Θ(1) Θ(1) Θ(1)
INSERT Θ(lg n) O(lg n) Θ(1)
MINIMUM Θ(1) O(lg n) Θ(1)
EXTRACT-MIN Θ(lg n) Θ(lg n) O(lg n)
UNION Θ(n) O(lg n) Θ(1)
DECREASE-KEY Θ(lg n) Θ(lg n) Θ(1)
DELETE Θ(lg n) Θ(lg n) O(lg n)
斐波那契堆，日后會(huì)在本BLOG內(nèi)，更進(jìn)一步的深入與具體闡述。且同時(shí)，此文，會(huì)不斷的加深與擴(kuò)展。
原文鏈接：http://blog.csdn.net/v_JULY_v/archive/2011/02/13/6182419.aspx
【編輯推薦】
