爲什麼我們不能將Dijkstra算法應用於負權重的圖形？

爲什麼我們不能將Dijkstra算法應用於負權重圖？爲什麼我們不能將Dijkstra算法應用於負權重的圖形？

來源

2010-07-08 prasanga

這個問題更適合math.stackexchange.com。因此，我建議將其重新安置。 – 2013-11-07 23:01:04

從A到B找到最便宜的路徑是什麼意思？如果您每次從C到D旅行，都會得到付費？

如果兩個節點之間存在負權重，那麼「最短路徑」將永遠在這兩個節點之間向後和向前循環。路徑越短，路徑越短。

這與算法無關，而且都與這種回答不可能性有關。

編輯：

上述權利要求假定雙向鏈路。如果沒有整體負面的體重週期，你沒有辦法永遠循環，獲得報酬。

在這種情況下，Dijkstra算法仍可能會失敗：

考慮兩個路徑：

該架向上的100成本，穿越其具有-25的最終邊緣之前的最佳路徑重量，給出總共75和
已經沒有與90

Dijkstra算法的總成本負加權邊緣的次優路徑將不變擬首先找到次優路徑，並在發現它時宣佈自己完成。它不會跟隨比找到的第一個解決方案更差的子路徑

來源

2010-07-08 03:17:55 Oddthinking

但是 - 只要沒有負重量循環，Bellman-Ford在負重力邊緣的情況下都能正常運行。所以有一些關於Dijkstra的算法會導致它失敗，即使你不能在一個負的權重循環中的兩個節點之間循環。 – dsolimano 2010-12-06 06:23:57

@dsolimano：是的。考慮兩條路徑：（1）一條最優路徑，其總成本爲100，在穿過具有-25重量的最終邊緣之前，總共爲75，以及（2）不具有負加權的次優路徑邊的總成本爲90.迪傑斯特拉算法將首先調查次優路徑，並在發現它時宣佈自己完成。它永遠不會跟隨比找到的第一個解決方案更糟糕的子路徑。 – Oddthinking 2010-12-08 14:21:31

@Oddthinking：所以你知道實際的答案（是的，它與算法有關），所以你應該從評論到答案文本推廣它。 – 2012-10-15 09:50:49

想象一下，您有一個有向圖，其中有一個有向循環，並且圍繞該距離的總「距離」爲負權重。如果在從開始到結束頂點的路上，您可以通過該定向循環，則可以簡單地在定向循環周圍繞過任意次數。

這意味着你可以讓你穿過圖的路徑有一個無限的負距離（或有效地）。

但是，只要你的圖形周圍沒有定向週期，你就可以脫離使用Dijkstra算法，而不會有任何爆炸。

所有的說法，如果你有一個負權重圖，你可以使用Belman-Ford算法。但是，由於這種算法的普遍性，它有點慢。 Bellman-Ford算法需要O（V·E），其中Dijkstra的時間爲O（E + VlogV）時間

來源

2012-04-19 02:52:59 theJollySin

我會給你一個反例。請考慮以下圖

http://img853.imageshack.us/img853/7318/3fk8.png

假設你在頂點A開始，要D最短路徑。Dijkstra算法會做以下步驟：

所訪問，並添加頂點B和C排隊
以最小距離隊列頂點獲取馬克A。它是B
標記B作爲訪問和添加頂點D隊列。
從隊列中提取。不是頂點D。
馬克D所訪問

的Dijkstra說從A到D最短路徑長度爲2，但它顯然是不正確的。

來源

2013-11-07 22:27:46 tomas789

爲什麼我們不能將Dijkstra算法應用於負權重的圖形？

回答

相關問題