本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。

經(jīng)典算法研究系列：二、Dijkstra 算法初探

 July   二零一一年一月

======================

本文主要參考：算法導(dǎo)論 第二版、維基百科。

寫的不好之處，還望見諒。
本經(jīng)典算法研究系列文章，永久勘誤，永久更新、永久維護(hù)。
   July、二零一一年二月十日更新。

------------------------------------

一、A*搜索算法

三、dynamic programming

二、Dijkstra 算法

五（續(xù)）、教你透徹了解紅黑樹

五、紅黑樹算法的實現(xiàn)與剖析

六、教你從頭到尾徹底理解KMP算法

四、BFS和DFS優(yōu)先搜索算法 

--------------------------------------

一、Dijkstra 算法的介紹

Dijkstra 算法，又叫迪科斯徹算法（Dijkstra），
算法解決的是有向圖中單個源點(diǎn)到其他頂點(diǎn)的最短路徑問題。
舉例來說，
如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示著城市間開車行經(jīng)的距離，
Dijkstra 算法可以用來找到兩個城市之間的最短路徑。

二、Dijkstra 的算法實現(xiàn)

Dijkstra 算法的輸入包含了一個有權(quán)重的有向圖 G，以及G中的一個來源頂點(diǎn) S。
我們以 V 表示 G 中所有頂點(diǎn)的集合，以 E 表示G 中所有邊的集合。
(u, v) 表示從頂點(diǎn) u 到 v 有路徑相連，而邊的權(quán)重則由權(quán)重函數(shù) w: E → [0, ∞] 定義。

因此，w(u, v) 就是從頂點(diǎn) u 到頂點(diǎn) v 的非負(fù)花費(fèi)值（cost），邊的花費(fèi)可以想像成兩個頂點(diǎn)之間的距離。
任兩點(diǎn)間路徑的花費(fèi)值，就是該路徑上所有邊的花費(fèi)值總和。

已知有 V 中有頂點(diǎn) s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花費(fèi)路徑(例如，最短路徑)。
這個算法也可以在一個圖中，找到從一個頂點(diǎn) s 到任何其他頂點(diǎn)的最短路徑。

好，咱們來看下此算法的具體實現(xiàn)：

Dijkstra 算法的實現(xiàn)一（維基百科）：

u := Extract_Min(Q) 在頂點(diǎn)集合 Q 中搜索有最小的 d[u] 值的頂點(diǎn) u。這個頂點(diǎn)被從集合 Q 中刪除并返回給用戶。

d[v] := infinity
u := Extract_Min(Q)
d[v] > d[u] + w(u,v) d[v] := d[u] + w(u,v)
14 previous[v] := u

如果我們只對在 s 和 t 之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足 u = t 的話終止程序。
現(xiàn)在我們可以通過迭代來回溯出 s 到 t 的最短路徑

1 s := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]

現(xiàn)在序列 S 就是從 s 到 t 的最短路徑的頂點(diǎn)集. 

Dijkstra 算法的實現(xiàn)二（算法導(dǎo)論）：

DIJKSTRA(G, w, s)

Q ≠ Ø
S ← S ∪{u}
RELAX(u, v, w) //松弛技術(shù)，E*O（1），E*O（lgV）。

因為dijkstra算法總是在V-S中選擇“最輕”或“最近”的頂點(diǎn)插入到集合S中，所以我們說它使用了貪心策略。

（貪心算法會在日后的博文中詳細(xì)闡述）。

===========================================

二零一一年二月九日更新：
此Dijkstra 算法的最初的時間復(fù)雜度為O（V*V+E），源點(diǎn)可達(dá)的話，O（V*lgV+E*lgV）=>O（E*lgV）
當(dāng)是稀疏圖的情況時，E=V*V/lgV，算法的時間復(fù)雜度可為O（V^2）。

但我們知道，若是斐波那契堆實現(xiàn)優(yōu)先隊列的話，算法時間復(fù)雜度，則為O（V*lgV + E）。

三、Dijkstra 算法的執(zhí)行速度

我們可以用大O符號將Dijkstra 算法的運(yùn)行時間表示為邊數(shù) m 和頂點(diǎn)數(shù) n 的函數(shù)。Dijkstra 算法最簡單的實現(xiàn)方法是用一個鏈表或者數(shù)組來存儲所有頂點(diǎn)的集合 Q，
所以搜索 Q 中最小元素的運(yùn)算（Extract-Min(Q)）只需要線性搜索 Q 中的所有元素。
這樣的話算法的運(yùn)行時間是 O(E^2)。

對于邊數(shù)少于 E^2 的稀疏圖來說，我們可以用鄰接表來更有效的實現(xiàn)迪科斯徹算法。
同時需要將一個二叉堆或者斐波納契堆用作優(yōu)先隊列來尋找最小的頂點(diǎn)（Extract-Min）。

當(dāng)用到二叉堆時候，算法所需的時間為O(( V+E )logE)，
斐波納契堆能稍微提高一些性能，讓算法運(yùn)行時間達(dá)到O(V+ElogE)。(此處一月十六日修正。)

 
開放最短路徑優(yōu)先（OSPF， Open Shortest Path First）算法是迪科斯徹算法在網(wǎng)絡(luò)路由中的一個具體實現(xiàn)。
與 Dijkstra 算法不同，Bellman-Ford算法可用于具有負(fù)數(shù)權(quán)值邊的圖，只要圖中不存在總花費(fèi)為負(fù)值且從源點(diǎn) s 可達(dá)的環(huán)路即可用此算法（如果有這樣的環(huán)路，則最短路徑不存在，因為沿環(huán)路循環(huán)多次即可無限制的降低總花費(fèi)）。

與最短路徑問題相關(guān)最有名的一個問題是旅行商問題（Traveling salesman problem），此類問題要求找出恰好通過所有標(biāo)點(diǎn)一次且最終回到原點(diǎn)的最短路徑。
然而該問題為NP-完全的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間解法。
如果有已知信息可用來估計某一點(diǎn)到目標(biāo)點(diǎn)的距離，則可改用A*搜尋算法，以減小最短路徑的搜索范圍。

=========================================

二零一一年二月九日更新：
BFS、DFS、Kruskal、Prim、dijkstra算法時間復(fù)雜度的比較：
一般說來，我們知道，BFS，DFS算法的時間復(fù)雜度為O（V+E），
最小生成樹算法Kruskal、Prim算法的時間復(fù)雜度為O（E*lgV）。

而Prim算法若采用斐波那契堆實現(xiàn)的話，算法時間復(fù)雜度為O（E+V*lgV），當(dāng)|V|<<|E|時，E+V*lgV是一個較大的改進(jìn)。
//|V|<<|E|，=>O（E+V*lgV） << O（E*lgV），對吧。:D

Dijkstra 算法，斐波納契堆用作優(yōu)先隊列時，算法時間復(fù)雜度為O（V*lgV + E）。
//看到了吧，與Prim算法采用斐波那契堆實現(xiàn)時，的算法時間復(fù)雜度是一樣的。

所以我們，說，BFS、Prime、Dijkstra 算法是有相似之處的，單從各算法的時間復(fù)雜度比較看，就可窺之一二。

四、圖文解析 Dijkstra 算法

 ok，經(jīng)過上文有點(diǎn)繁雜的信息，你還并不對此算法了如指掌，清晰透徹。
沒關(guān)系，咱們來幅圖，就好了。請允許我再對此算法的概念闡述下，

dijkstra算法是典型最短路徑算法，用于計算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。
不過，針對的是非負(fù)值權(quán)邊。

主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，，直到擴(kuò)展到終點(diǎn)為止。
[dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點(diǎn)很多，所以效率低。]

ok，請看下圖：

如下圖，設(shè)A為源點(diǎn)，求A到其他各所有一一頂點(diǎn)（B、C、D、E、F）的最短路徑。線上所標(biāo)注為相鄰線段之間的距離，即權(quán)值。

（注：此圖為隨意所畫，其相鄰頂點(diǎn)間的距離與圖中的目視長度不能一一對等）

算法執(zhí)行步驟如下表：

是不是對此Dijkstra 算法有不錯的了解了。那么，此文也完了。:D。 

              ----July、2010年12月24日。平安夜。

==============================================

此文，寫的實在不怎么樣。不過，承蒙大家厚愛，此經(jīng)典算法研究系列的后續(xù)文章，個人覺得寫的還行。
所以，還請，各位可關(guān)注此算法系列的后續(xù)文章。謝謝。

                 二零一一年一月四日。

  本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。