Dijkstra演算法能否用於有環圖？

01-03

《演算法圖解》中說，Dijkstra演算法只適用於非負權值、有向無環圖中，非負權值以及有向我可以理解，就是這個無環我理解不了。
如果存在環，並不會影響節點的開銷計算啊，而且處理過的節點不再進行計算，不會造成死循環。
《演算法圖解》第100頁

看了假書吧，有環是可以的。

這個「眾所周知」都知了些什麼啊......我記得只有有負權的圖不適用於Dijkstra演算法啊

Dij可以用於有環圖。

堆優化的Dij甚至支持帶負環的圖（如果沒有負環就跑出結果，有則報告），但是這樣的話複雜度會退化到指數級。

用SPFA的鬆弛方式來寫Dij就行了。可以證明：在沒有負權邊的圖上，每個點只會被鬆弛一次（這時候與普通的Dij寫法複雜度一致，E logV）；同時也以低劣的複雜度支持了帶負權的圖（普通Dij不支持）。

大開眼界，居然有這種一本正經地胡說八道的書2333

只要邊權非負，複雜度和正確性都是對的呀...

（你看的是什麼野書

據我所知

dijkstra演算法應用於不含負權迴路的圖

有向無向均可

先問是不是，再問為什麼。

你可能學了假的演算法

不是負環吧。。。

你可能學了假的dij

dijkstra演算法的正確性依賴於圖中無負權邊，與有沒有環無關。這是因為如果有負邊，已經固定dis的點可能會被其它dis大於它的點更新。DAG上的單源最短路是可以求拓撲序之後線性求的，如果dijkstra只適用於DAG那它是沒什麼用的

都無環了為什麼不叫樹啊，

無環的話任意兩點間只有一條路了還談什麼最短

dijkstra就是為了從兩點之間的多條路徑中找到最小的那一條，在每一次迭代時，考慮了環的情況，對結果進行比較更新。如果無環，那麼所有的點兩兩之間就最多只有唯一路徑了（DAG可能路徑不存在）。

偽代碼如下：

將所有點的標號置為假

d[0] = 0, 其他 d[i] = INF

找出未標記的，且d[i] 最小的點 m

標記這個點為真

對與m連接的所有點n（無論是否被標記），更新 d[n] = min { d[n] , d[m] + w( m, n) }

如果是有向無環圖的話，你拓撲排序一下不就順便求出來了；如果是無向無環圖的話，你dfs一下不是更好……

你看的是假書……扔了吧……換本黑書

有向無環圖可以直接拓撲排序，再按照這個順序DP求最短路，複雜度O(n)，用Dijkstra簡直是殺雞用牛刀。

只要不出現負環都可以。

單源最短路徑（4）：總結單源最短路徑（1）：Dijkstra演算法

能

那dij有個屁用啊，無環圖不是可以直接O(V)嗎(