我很難理解爲什麼Dijkstra算法不適用於具有負邊的無環有向圖。據我所知，Dijkstra對圖形進行了廣度優先遍歷，在適當的時候放鬆。例如，考慮圖表：Dijkstra和負邊緣
S->A (3)
S->B (4)
B->A (-2)
其中S是源節點。這是我想象它的工作：與4
2）遞歸對A的距離，馬克B的距離
1）標誌由於A分沒有節點，什麼也不做。
3）在B上行走。由於B指向A，檢查B的距離+ B-> A是否小於A的當前距離。2 < 3，所以標記A的距離爲2
然而，顯然這不是它的工作原理，因爲我使用這本書給出了這張圖來說明底片爲什麼不起作用。我無法按照本書的解釋。 Dijkstra如何在這張圖表上工作，爲什麼他們不會使用我想象中的方法？
問題是，一旦你處理了一個節點，你不能在之後更新它的距離，因爲那樣會需要遞歸更新並且會拋棄整個東西（閱讀：違背節點處理算法的假設單調增加到源的距離;查看算法的正確性證明以查看需要的地方）。所以一旦A被處理完畢，你不能再改變它的距離，這意味着你不能有負邊緣，因爲它們可能會讓你距離以前處理過的節點更近。單調增加距離的假設是爲什麼在節點處理後將節點標記爲黑色，之後忽略黑色節點。因此即使在圖A中距離S到S的距離爲2，Dijkstra的算法會給你一個3的距離，因爲在A被處理之後，它忽略了通向A的任何邊。
編輯：下面是Dijkstra算法會做：
1）標誌爲3的距離，把它放到等待處理節點的隊列;標記B距離4，放入隊列中。
2）因爲它在前面，所以把A取出隊列。由於A指向沒有節點，所以不要更新任何距離，不要向隊列添加任何內容。標記爲已處理。
3）將B帶出隊列。 B指向A，但A被標記爲已處理;忽略邊B-→A。由於B不再有輸出邊緣，我們就完成了。
編輯2： 關於DAG，根本不需要Dijkstra算法。 DAG始終有一個拓撲排序，可以在O（| V | + | E |）中計算，並使用d(w) = min {d(w); d(v) + c(v, w)}作爲更新距離的規則來處理拓撲順序中的頂點，其中d(v)是頂點v與頂點之間的距離源和c(v,w)是邊緣的長度(v,w)會給你正確的距離，再次在O（| V | + | E |）。總共有兩個步驟，每個都需要O（| V | + | E |），所以這是計算具有任意邊長度的DAG中的單源最短路徑的總複雜度。