前言
由于上限為O(NM) = O(VE)的SPFA算法的時間復(fù)雜度，卡死的概率非常高。在算法競賽中，我們需要一個更穩(wěn)定的算法:dijkstra。
什么是dijkstra？
Dijkstra是單源最短路徑算法，時間復(fù)雜度上限為O(n ^ 2)(naive)，在實際應(yīng)用中相對穩(wěn)定。堆優(yōu)化后有O((n+m)log_{2}n的時間復(fù)雜度，在密集圖中表現(xiàn)良好。
Dijkstra的原理/過程？
Dijkstra的本質(zhì)是貪婪，只適用于沒有負(fù)權(quán)邊的圖。
我們把點(diǎn)分為兩類，一類是確定最短路徑的點(diǎn)，稱為“白點(diǎn)”，另一類是沒有確定最短路徑的點(diǎn)，稱為“藍(lán)點(diǎn)”
Dijkstra的流程如下:
1.初始化dis[start] = 0，其他節(jié)點(diǎn)的dis值為無窮大。
2.找一個dis值最小的藍(lán)點(diǎn)X，把節(jié)點(diǎn)X變成白點(diǎn)。
遍歷x的所有輸出邊(x，y，z)，如果dis [y]>:用dis[x]+z，讓dis[y] = dis[x]+z
4.重復(fù)步驟2和3，直到所有點(diǎn)都變成白色斑點(diǎn)。
時間復(fù)雜度為O (n 2)
為什么dijkstra是正確的
當(dāng)所有邊長都為非負(fù)時，全局最小值不能被其他節(jié)點(diǎn)更新。因此，在步驟2中找到的藍(lán)點(diǎn)X必須滿足dis[x]是從起點(diǎn)到X的最短路徑，我們不斷選擇全局最小值進(jìn)行標(biāo)記和擴(kuò)展，最終可以得到從起點(diǎn)到每個節(jié)點(diǎn)的最短路徑長度
示意圖
(make start = 1)
一開始，我們將dis[start]初始化為0，其他點(diǎn)初始化為inf
例子入門模板:P3371
高級模板:P4779
其他例子，請右轉(zhuǎn)至洛谷題庫，搜索“最短路徑”
附筆
本文的一部分摘自李玉東的算法競賽和信息學(xué)奧林匹克競賽高級指南
友情提示:正權(quán)重圖請使用dijkstra算法，負(fù)權(quán)重圖請使用SPFA算法
感謝洛谷管理員提供的平臺
這篇文章是小孫在《洛谷日報》上發(fā)表的
原地址:https://www.luogu.org/blog/61966/dijkstra
1.《dijkstra算法過程圖解 [洛谷日報第31期]dijkstra詳解》援引自互聯(lián)網(wǎng)，旨在傳遞更多網(wǎng)絡(luò)信息知識，僅代表作者本人觀點(diǎn)，與本網(wǎng)站無關(guān)，侵刪請聯(lián)系頁腳下方聯(lián)系方式。
2.《dijkstra算法過程圖解 [洛谷日報第31期]dijkstra詳解》僅供讀者參考，本網(wǎng)站未對該內(nèi)容進(jìn)行證實，對其原創(chuàng)性、真實性、完整性、及時性不作任何保證。
3.文章轉(zhuǎn)載時請保留本站內(nèi)容來源地址，http://f99ss.com/yule/1019107.html
