作者：July 二零一一年二月十三日。
參考代碼：introduction to algorithms，Second Edition。
---------------------------------------
了解什麼是Dijkstra 算法，請參考：html">http://www.BkJia.com/kf/201104/87374.html
本文由單源最短路徑路徑問題開始，而後描述Bellman-Ford算法，到具體闡述Dijkstra算法，
闡述詳細剖析Dijkstra算法的每一個步驟，教你徹底理解此Dijkstra算法。
一、單源最短路徑問題
我們知道，單源最短路徑問題：已知圖G=(V，E)，要求找出從某個定源頂點s<-V，到每個v<-V的最短路徑。
簡單來說，就是一個圖G中，找到一個定點s，然後以s為起點，要求找出s到圖G中其余各個點的最短距離或路徑。
此單源最短路徑問題有以下幾個變形：
I、 單終點最短路徑問題：
每個頂點v到指定終點t的最短路徑問題。即單源最短路徑問題的相對問題。
II、 單對頂點最短路徑問題：
給定頂點u和v，找出從u到v的一條最短路徑。
III、每對頂點間最短路徑問題：
針對任意每倆個頂點u和v，找出從u到v的最短路徑。
最簡單的想法是，將每個頂點作為源點，運行一次單源算法即可以解決這個問題。
當然，還有更好的辦法，日後在本BOlG內闡述。
二、Bellman-Ford 算法
1、回路問題
一條最短路徑不能包含負權回路，也不能包含正權回路。
一些最短路徑的算法，如Dijkstra 算法，要求圖中所有的邊的權值都是非負的，如在公路地圖上，找一條從定點s到目的頂點v的最短路徑問題。
2、Bellman-Ford 算法
而Bellman-Ford 算法，則允許輸入圖中存在負權邊，只要不存在從源點可達的負權回路，即可。
簡單的說，圖中可以存在負權邊，但此條負權邊，構不成負權回路，不影響回路的形成。
且，Bellman-Ford 算法本身，便是可判斷圖中是否存在從源點可達的負權回路，
若存在負權回路，算法返回FALSE,若不存在，返回TRUE。
Bellman-Ford 算法的具體描述
BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) //對每個頂點初始化 ，O(V)
2 for i ← 1 to |V[G]| - 1
3 do for each edge (u, v) ∈ E[G]
4 do RELAX(u, v, w) //針對每個頂點(V-1個)，都運用松弛技術O(E)，計為O（(v-1)*E)）
5 for each edge (u, v) ∈ E[G]
6 do if d[v] > d[u] + w(u, v)
7 then return FALSE //檢測圖中每條邊，判斷是否包含負權回路，
//若d[v]>d[u]+w(u，v)，則表示包含，返回FALSE，
8 return TRUE //不包含負權回路，返回TRUE
Bellman-Ford 算法的時間復雜度，由上可得為O（V*E）。
3、關於判斷圖中是否包含負權回路的問題：
根據定理，我們假定，u是v的父輩，或父母，那麼
當G(V,E)是一個有向圖或無向圖(且不包含任何負權回路)，s<-V，s為G的任意一個頂點，則對任意邊(u，v)<-V，有
d[s，v] <= d[s，u]+1
此定理的詳細證明，可參考算法導論一書上，第22章中引理22.1的證明。
或者根據第24章中通過三角不等式論證Bellman-Ford算法的正確性，也可得出上述定理的變形。
即假設圖G中不包含負權回路，可證得
d[v]=$(s，u)
<=$(s，u)+w(u，v) //根據三角不等式
=d[u]+w[u，v]
所以，在不包含負權回路的圖中，是可以得出d[v]<=d[u]+w(u，v)。
於是，就不難理解，在上述Bellman-Ford 算法中，
if d[v] > d[u]+w(u，v)，=> 包含負權回路，返回FASLE
else if =>不包含負權回路，返回TRUE。
ok，咱們，接下來，立馬切入Dijkstra 算法。
三、深入淺出，徹底解剖Dijkstra 算法
I、松弛技術RELAX的介紹
Dijkstra 算法使用了松弛技術，對每個頂點v<-V，都設置一個屬性d[v]，用來描述從源點s到v的最短路徑上權值的上界，
稱為最短路徑的估計。
首先，得用O（V）的時間，來對最短路徑的估計，和對前驅進行初始化工作。
INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v ∈ V[G]
2 do d[v] ← ∞
3 π[v] ← NIL //O（V）
4 d[s] 0
RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 then d[v] ← d[u] + w(u, v)
3 π[v] ← u //O（E）
圖。
II、Dijkstra 算法
此Dijkstra 算法分三個步驟，
INSERT (第3行), EXTRACT-MIN (第5行), 和DECREASE-KEY(第8行的RELAX，調用此減小關鍵字的操作)。
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) //對每個頂點初始化 ，O(V)
2 S ← Ø
3 Q ← V[G] //INSERT，O(1)
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //簡單的O(V*V)；二叉/項堆，和FIB-HEAP的話，則都為O(V*lgV)。
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //簡單方式:O(E)，二叉/項堆，E*O(lgV)，FIB-HEAP，E*O(1)。
四、Dijkstra 算法的運行時間
在繼續闡述之前，得先聲明一個問題，DIJKSTRA（G，w，s）算法中的第5行，EXTRACT-MIN(Q)，最小優先隊列的具體實現。
而Dijkstra 算法的運行時間，則與此最小優先隊列的采取何種具體實現，有關。
最小優先隊列三種實現方法：
1、利用從1至|V| 編好號的頂點，簡單地將每一個d[v]存入一個數組中對應的第v項，
如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的運行時間為O(V^2+E)。
2、如果是二叉/項堆實現最小優先隊列的話，EXTRACT-MIN(Q)的運行時間為O(V*lgV)，
所以，Dijkstra 算法的運行時間為O(V*lgV+E*lgV)，
若所有頂點都是從源點可達的話，O（(V+E)*lgV）=O（E*lgV）。
當是稀疏圖時，則E=O(V^2/lgV)，此Dijkstra 算法的運行時間為O(V^2)。
3、采用斐波那契堆實現最小優先隊列的話，EXTRACT-MIN(Q)的運行時間為O(V*lgV)，
所以，此Dijkstra 算法的運行時間即為O(V*lgV+E)。
綜上所述，此最小優先隊列的三種實現方法比較如下：
EXTRACT-MIN + RELAX
I、 簡單方式： O（V*V + E*1）
II、 二叉/項堆： O（V*lgV + |E|*lgV）
源點可達：O（E*lgV）
稀疏圖時，有E=o（V^2/lgV），
=> O（V^2）
III、斐波那契堆：O（V*lgV + E）
當|V|<<|E|時，采用DIJKSTRA（G，w，s）+ FIB-HEAP-EXTRACT-MIN(Q)，即斐波那契堆實現最小優先隊列的話，
優勢就體現出來了。
五、Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)，斐波那契堆實現最小優先隊列
由以上內容，我們已經知道，用斐波那契堆來實現最小優先隊列，可以將運行時間提升到O（VlgV+E）。
|V|個EXTRACT-MIN 操作，每個平攤代價為O（lgV），|E|個DECREASE-KEY操作的每個平攤時間為O（1）。
下面，重點闡述DIJKSTRA(G, w, s)中，斐波那契堆實現最小優先隊列的操作。
由上，我們已經知道，DIJKSTRA算法包含以下的三個步驟：
INSERT (第3行), EXTRACT-MIN (第5行), 和DECREASE-KEY(第8行的RELAX)。
先直接給出Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)的算法：
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← Ø
3 Q ← V[G] //第3行，INSERT操作，O（1）
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //第5行，EXTRACT-MIN操作，V*lgV
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 &
