免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

　　SPFA 算法由于它上限 O(NM) = O(VE) 的時(shí)間復(fù)雜度,被卡掉的幾率很大.在算法競(jìng)賽中,我們需要一個(gè)更穩(wěn)定的算法: dijkstra .

　　什么是 dijkstra ?

　　dijkstra 是一種單源最短路徑算法,時(shí)間復(fù)雜度上限為 O(n^2) (樸素),在實(shí)際應(yīng)用中較為穩(wěn)定 ; 加上堆優(yōu)化之后更是具有 O((n+m)\log_{2}n) 的時(shí)間復(fù)雜度,在稠密圖中有不俗的表現(xiàn).

　　dijkstra 的原理/流程?

　　dijkstra 本質(zhì)上的思想是貪心,它只適用于不含負(fù)權(quán)邊的圖.

　　我們把點(diǎn)分成兩類,一類是已經(jīng)確定最短路徑的點(diǎn),稱為"白點(diǎn)",另一類是未確定最短路徑的點(diǎn),稱為"藍(lán)點(diǎn)"

　　dijkstra 的流程如下 :

　　1. 初始化 dis[start] = 0, 其余節(jié)點(diǎn)的 dis 值為無(wú)窮大.

　　2. 找一個(gè) dis 值最小的藍(lán)點(diǎn) x, 把節(jié)點(diǎn) x 變成白點(diǎn).

　　3. 遍歷 x 的所有出邊 (x,y,z), 若 dis[y] > dis[x] + z, 則令 dis[y] = dis[x] + z

　　4. 重復(fù) 2,3 兩步,直到所有點(diǎn)都成為白點(diǎn) .

　　時(shí)間復(fù)雜度為 O(n^2)

　　dijkstra 為什么是正確的

　　當(dāng)所有邊長(zhǎng)都是非負(fù)數(shù)的時(shí)候,全局最小值不可能再被其他節(jié)點(diǎn)更新.所以在第 2 步中找出的藍(lán)點(diǎn) x 必然滿足 :dis[x] 已經(jīng)是起點(diǎn)到 x 的最短路徑 . 我們不斷選擇全局最小值進(jìn)行標(biāo)記和拓展,最終可以得到起點(diǎn)到每個(gè)節(jié)點(diǎn)的最短路徑的長(zhǎng)度

　　圖解

　　(令 start = 1 )

　　開(kāi)始時(shí)我們把 dis[start] 初始化為 0 ,其余點(diǎn)初始化為 inf

　　

第一輪循環(huán)找到 dis 值最小的點(diǎn) 1 ,將 1 變成白點(diǎn),對(duì)所有與 1 相連的藍(lán)點(diǎn)的 dis 值進(jìn)行修改,使得 dis[2]=2,dis[3]=4,dis[4]=7
第二輪循環(huán)找到 dis 值最小的點(diǎn) 2 ,將 2 變成白點(diǎn),對(duì)所有與 2 相連的藍(lán)點(diǎn)的 dis 值進(jìn)行修改,使得 dis[3]=3,dis[5]=4
第三輪循環(huán)找到 dis 值最小的點(diǎn) 3 ,將 3 變成白點(diǎn),對(duì)所有與 2 相連的藍(lán)點(diǎn)的 dis 值進(jìn)行修改,使得 dis[4]=4
接下來(lái)兩輪循環(huán)分別將 4,5 設(shè)為白點(diǎn),算法結(jié)束,求出所有點(diǎn)的最短路徑

　　時(shí)間復(fù)雜度 O(n^2)

　　為什么 dijkstra 不能處理有負(fù)權(quán)邊的情況?

　　我們來(lái)看下面這張圖

　　

　　2 到 3 的邊權(quán)為 -4 ,顯然從 1 到 3 的最短路徑為 -2 (1->2->3). 但在循環(huán)開(kāi)始時(shí)程序會(huì)找到當(dāng)前 dis 值最小的點(diǎn) 3 ,并標(biāo)記它為白點(diǎn).

　　這時(shí)的 dis[3]=1, 然而 1 并不是起點(diǎn)到 3 的最短路徑.因?yàn)?3 已經(jīng)被標(biāo)為白點(diǎn),所以 dis[3] 不會(huì)再被修改了.我們?cè)谶厵?quán)存在負(fù)數(shù)的情況下得到了錯(cuò)誤的答案.

　　dijkstra 的堆優(yōu)化?

　　觀察 dijkstra 的流程,發(fā)現(xiàn)步驟 2 可以優(yōu)化

　　怎么優(yōu)化呢?

　　我會(huì)zkw線段樹(shù)!我會(huì)斐波那契堆!

　　我會(huì)堆!

　　我們可以用堆對(duì) dis 數(shù)組進(jìn)行維護(hù),用 O(\log_{2}n) 的時(shí)間取出堆頂元素并刪除,用 O(\log_{2}n) 遍歷每條邊,總復(fù)雜度 O((n+m)\log_{2}n)

　　范例代碼: