SPFA 算法由于它上限 O(NM) = O(VE) 的時間復(fù)雜度,被卡掉的幾率很大.在算法競賽中,我們需要一個更穩(wěn)定的算法: dijkstra .
什么是 dijkstra ?
dijkstra 是一種單源最短路徑算法,時間復(fù)雜度上限為 O(n^2) (樸素),在實際應(yīng)用中較為穩(wěn)定 ; 加上堆優(yōu)化之后更是具有 O((n+m)\log_{2}n) 的時間復(fù)雜度,在稠密圖中有不俗的表現(xiàn).
dijkstra 的原理/流程?
dijkstra 本質(zhì)上的思想是貪心,它只適用于不含負(fù)權(quán)邊的圖.
我們把點分成兩類,一類是已經(jīng)確定最短路徑的點,稱為"白點",另一類是未確定最短路徑的點,稱為"藍點"
dijkstra 的流程如下 :
1. 初始化 dis[start] = 0, 其余節(jié)點的 dis 值為無窮大.
2. 找一個 dis 值最小的藍點 x, 把節(jié)點 x 變成白點.
3. 遍歷 x 的所有出邊 (x,y,z), 若 dis[y] > dis[x] + z, 則令 dis[y] = dis[x] + z
4. 重復(fù) 2,3 兩步,直到所有點都成為白點 .
時間復(fù)雜度為 O(n^2)
dijkstra 為什么是正確的
當(dāng)所有邊長都是非負(fù)數(shù)的時候,全局最小值不可能再被其他節(jié)點更新.所以在第 2 步中找出的藍點 x 必然滿足 :dis[x] 已經(jīng)是起點到 x 的最短路徑 . 我們不斷選擇全局最小值進行標(biāo)記和拓展,最終可以得到起點到每個節(jié)點的最短路徑的長度
圖解
(令 start = 1 )
開始時我們把 dis[start] 初始化為 0 ,其余點初始化為 inf
時間復(fù)雜度 O(n^2)
為什么 dijkstra 不能處理有負(fù)權(quán)邊的情況?
我們來看下面這張圖
2 到 3 的邊權(quán)為 -4 ,顯然從 1 到 3 的最短路徑為 -2 (1->2->3). 但在循環(huán)開始時程序會找到當(dāng)前 dis 值最小的點 3 ,并標(biāo)記它為白點.
這時的 dis[3]=1, 然而 1 并不是起點到 3 的最短路徑.因為 3 已經(jīng)被標(biāo)為白點,所以 dis[3] 不會再被修改了.我們在邊權(quán)存在負(fù)數(shù)的情況下得到了錯誤的答案.
dijkstra 的堆優(yōu)化?
觀察 dijkstra 的流程,發(fā)現(xiàn)步驟 2 可以優(yōu)化
怎么優(yōu)化呢?
我會zkw線段樹!我會斐波那契堆!
我會堆!
我們可以用堆對 dis 數(shù)組進行維護,用 O(\log_{2}n) 的時間取出堆頂元素并刪除,用 O(\log_{2}n) 遍歷每條邊,總復(fù)雜度 O((n+m)\log_{2}n)
范例代碼:
