Dijkstra 算法初探
Dijkstra 算法，又叫迪科斯徹算法（Dijkstra），算法解決的是有向圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題。
舉例來說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示著城市間開車行經(jīng)的距離，Dijkstra 算法可以用來找到兩個(gè)城市之間的最短路徑。
一、Dijkstra 的算法實(shí)現(xiàn)
Dijkstra 算法的輸入包含了一個(gè)有權(quán)重的有向圖 G，以及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)可以想像成兩個(gè)頂點(diǎn)之間的距離。任兩點(diǎn)間路徑的花費(fèi)值，就是該路徑上所有邊的花費(fèi)值總和。
已知有 V 中有頂點(diǎn) s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花費(fèi)路徑(例如，最短路徑)。這個(gè)算法也可以在一個(gè)圖中，找到從一個(gè)頂點(diǎn) s 到任何其他頂點(diǎn)的最短路徑。
好，咱們來看下此算法的具體實(shí)現(xiàn)：
Dijkstra 算法的實(shí)現(xiàn)一（維基百科）：
u := Extract_Min(Q) 在頂點(diǎn)集合 Q 中搜索有最小的 d[u] 值的頂點(diǎn) u。這個(gè)頂點(diǎn)被從集合 Q 中刪除并返回給用戶。
- function Dijkstra(G, w, s)
- for each vertex v in V[G] // 初始化
- d[v] := infinity
- previous[v] := undefined
- d[s] := 0
- S := empty set
- Q := set of all vertices
- while Q is not an empty set // Dijkstra演算法主體
- u := Extract_Min(Q)
- S := S union {u}
- for each edge (u,v) outgoing from u
- if d[v] > d[u] + w(u,v) // 拓展邊（u,v）
- d[v] := d[u] + w(u,v)
- previous[v] := u
如果我們只對(duì)在 s 和 t 之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足 u = t 的話終止程序。現(xiàn)在我們可以通過迭代來回溯出 s 到 t 的最短路徑.
- s := empty sequence
- u := t
- while defined u
- insert u to the beginning of S
- u := previous[u]
現(xiàn)在序列 S 就是從 s 到 t 的最短路徑的頂點(diǎn)集.
Dijkstra 算法的實(shí)現(xiàn)二（算法導(dǎo)論）：
- DIJKSTRA(G, w, s)
- INITIALIZE-SINGLE-SOURCE(G, s)
- S ← Ø
- Q ← V[G] //V*O（1）
- while Q ≠ Ø
- do u ← EXTRACT-MIN(Q) //EXTRACT-MIN，V*O（V），V*O（lgV）
- S ← S ∪{u}
- for each vertex v ∈ Adj[u]
- do RELAX(u, v, w) //松弛技術(shù)，E*O（1），E*O（lgV）。
因?yàn)镈ijkstra算法總是在V-S中選擇“最輕”或“最近”的頂點(diǎn)插入到集合S中，所以我們說它使用了貪心策略。
此Dijkstra 算法的最初的時(shí)間復(fù)雜度為O（V*V+E），源點(diǎn)可達(dá)的話，O（V*lgV+E*lgV）=>O（E*lgV）
當(dāng)是稀疏圖的情況時(shí)，E=V*V/lgV，算法的時(shí)間復(fù)雜度可為O（V^2）。
但我們知道，若是斐波那契堆實(shí)現(xiàn)優(yōu)先隊(duì)列的話，算法時(shí)間復(fù)雜度，則為O（V*lgV + E）。
二、Dijkstra 算法的執(zhí)行速度
我們可以用大O符號(hào)將Dijkstra 算法的運(yùn)行時(shí)間表示為邊數(shù) m 和頂點(diǎn)數(shù) n 的函數(shù)。Dijkstra 算法最簡單的實(shí)現(xiàn)方法是用一個(gè)鏈表或者數(shù)組來存儲(chǔ)所有頂點(diǎn)的集合 Q，所以搜索 Q 中最小元素的運(yùn)算（Extract-Min(Q)）只需要線性搜索 Q 中的所有元素。
這樣的話算法的運(yùn)行時(shí)間是 O(E^2)。
對(duì)于邊數(shù)少于 E^2 的稀疏圖來說，我們可以用鄰接表來更有效的實(shí)現(xiàn)迪科斯徹算法。同時(shí)需要將一個(gè)二叉堆或者斐波納契堆用作優(yōu)先隊(duì)列來尋找最小的頂點(diǎn)（Extract-Min）。
當(dāng)用到二叉堆時(shí)候，算法所需的時(shí)間為O(( V+E )logE)，斐波納契堆能稍微提高一些性能，讓算法運(yùn)行時(shí)間達(dá)到O(V+ElogE)。
開放最短路徑優(yōu)先（OSPF， Open Shortest Path First）算法是迪科斯徹算法在網(wǎng)絡(luò)路由中的一個(gè)具體實(shí)現(xiàn)。與 Dijkstra 算法不同，Bellman-Ford算法可用于具有負(fù)數(shù)權(quán)值邊的圖，只要圖中不存在總花費(fèi)為負(fù)值且從源點(diǎn) s 可達(dá)的環(huán)路即可用此算法（如果有這樣的環(huán)路，則最短路徑不存在，因?yàn)檠丨h(huán)路循環(huán)多次即可無限制的降低總花費(fèi)）。
與最短路徑問題相關(guān)最有名的一個(gè)問題是旅行商問題（Traveling salesman problem），此類問題要求找出恰好通過所有標(biāo)點(diǎn)一次且最終回到原點(diǎn)的最短路徑。
然而該問題為NP-完全的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項(xiàng)式時(shí)間解法。如果有已知信息可用來估計(jì)某一點(diǎn)到目標(biāo)點(diǎn)的距離，則可改用A*搜尋算法，以減小最短路徑的搜索范圍。
BFS、DFS、Kruskal、Prim、Dijkstra算法時(shí)間復(fù)雜度的比較：
一般說來，我們知道，BFS，DFS算法的時(shí)間復(fù)雜度為O（V+E），最小生成樹算法Kruskal、Prim算法的時(shí)間復(fù)雜度為O（E*lgV）。而Prim算法若采用斐波那契堆實(shí)現(xiàn)的話，算法時(shí)間復(fù)雜度為O（E+V*lgV），當(dāng)|V|<<|E|時(shí)，E+V*lgV是一個(gè)較大的改進(jìn)。//|V|<<|E|，=>O（E+V*lgV） << O（E*lgV），對(duì)吧。
Dijkstra 算法，斐波納契堆用作優(yōu)先隊(duì)列時(shí)，算法時(shí)間復(fù)雜度為O（V*lgV + E）。//看到了吧，與Prim算法采用斐波那契堆實(shí)現(xiàn)時(shí)，的算法時(shí)間復(fù)雜度是一樣的。
所以我們，說，BFS、Prime、Dijkstra 算法是有相似之處的，單從各算法的時(shí)間復(fù)雜度比較看，就可窺之一二。
三、圖文解析 Dijkstra 算法
經(jīng)過上文有點(diǎn)繁雜的信息，你還并不對(duì)此算法了如指掌，清晰透徹。沒關(guān)系，咱們來幅圖，就好了。請(qǐng)?jiān)试S我再對(duì)此算法的概念闡述下，
Dijkstra算法是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。
不過，針對(duì)的是非負(fù)值權(quán)邊。
主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。
[Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。
請(qǐng)看下圖：
如下圖，設(shè)A為源點(diǎn)，求A到其他各所有一一頂點(diǎn)（B、C、D、E、F）的最短路徑。線上所標(biāo)注為相鄰線段之間的距離，即權(quán)值。
（注：此圖為隨意所畫，其相鄰頂點(diǎn)間的距離與圖中的目視長度不能一一對(duì)等）
Dijkstra無向圖
算法執(zhí)行步驟如下表：
是不是對(duì)此Dijkstra 算法有不錯(cuò)的了解了。那么，此文也完了。
原文鏈接：http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx
【編輯推薦】
