Dijkstra的負重算法

好的，首先我知道Dijkstra不適用於負重，我們可以使用Bellman-ford來代替它。但是在一個問題中，我給出了它的所有邊都有從0到1的權重（0和1不包括在內）。而路徑的成本實際上就是產品。Dijkstra的負重算法

所以我在想的就是取日誌。現在所有的邊緣都是負面的。現在我知道迪克斯特拉不會爲負面權重工作，但在這種情況下，所有的邊緣都是負面的，所以我們不能做點什麼來讓迪克斯特拉工作。

我雖然所有的權重乘以-1，但最短的路徑成爲最長的路徑。

因此，無論如何，我可以避免在這種情況下的貝爾曼 - 福特算法。

確切的問題是：「假設對於某些應用，路徑的成本等於路徑中所有邊的權重乘積。在這種情況下，您將如何使用Dijkstra算法？所有權重邊緣從0到1（0和1不包括在內）「。

來源

2015-04-18 George J. Adams

首先，我假設圖是指向的。現在，如果權重在0到1之間，並且成本是通過權重的乘積來衡量的，那麼您的確在尋找最長的路徑。如果圖中有任何週期，那麼它相當於一個負成本週期。 –

因此Dijkstra會工作。我只需要找到最長的路徑。另外，沒有額外的要求，因此我很困惑。 –

你確定你不想要最可能的路徑嗎？ –

所以，你想用一個函數，比如說F，你將應用於原始圖的權重，然後用Dijkstra的算法找到最短的產品路徑。我們還要考慮以下圖中，我們從節點A開始，其中0 < x < y < 1：

Second graph

在上圖中F(x)必須比F(y)較小的Dijkstra算法正確輸出的最短路徑從A。

現在，讓我們來稍微不同的曲線圖，我們從節點A重新開始：

First graph

然後Dijkstra算法是如何工作的？

由於F(x) < F(y)那麼我們將在下一步選擇節點B。然後我們將訪問剩餘的節點C。Dijkstra算法將輸出從A到B的最短路徑是A -> B從A到C的最短路徑是A -> C。

但是從A到B的最短路徑是A -> C -> B，成本x * y < x。

這意味着我們無法找到一個重量轉換功能，並期望Dijkstra算法，以在任何情況下工作。

來源

2015-04-18 11:02:18 JuniorCompressor

如果圖表上的所有權重都在(0, 1)範圍內，那麼總會有一個重量小於1的週期，因此您將永遠停留在此週期中（每循環一次就會減少最短路徑的總重量）。可能你錯誤地理解了這個問題，你要麼找到最長的路徑，要麼你不允許兩次訪問同一個頂點。無論如何，在第一種情況下，即使沒有log修改，dijkstra'a算法也是絕對適用的。我很確定第二種情況不能用多項式複雜度來解決。

來源

2015-04-18 09:52:41

如果我們不允許兩次訪問同一個頂點，該怎麼辦？ –

@GeorgeAdams這是我在回答中提到的第二個案例。你可以減少你的問題找到最長的路徑，因此沒有已知的多項式解決方案（查看本文：http://cstheory.stackexchange.com/questions/17462/finding-the-shortest-path-in-the - 負循環的呈現） –

完美答案。 Just nit picking：你可以減少找到最長的路徑，這就是證明NP硬度。 –

您寫道：

我雖然-1所有的權重，但隨後的最短路徑成爲最長路徑相乘。

要在最短路徑和最長路徑之間切換權重。所以1/3將是3,5將是1/5等。

來源

2015-04-18 10:36:47

但是，如果你反過來，它不會再給出同樣的答案。假設你有dist（a，c）= 1，dist（a，b）= 2，dist（b，c）= 2。最長的路徑是a-b-c cost 4.如果反過來，我們有dist（a，c）= 1，dist（a，b）= 0.5，dist（b，c）= 0.5。這裏a-b-c和a-c具有相同的最短路徑。 – justhalf

如果你的圖有個週期，沒有最短路徑算法會找到答案，因爲這些週期將永遠是「負循環」，作爲Rontogiannis Aristofanis指出。

如果你的圖表沒有周期，你不必使用Dijkstra的所有。

如果它被引導，這是一個DAG和有線性時間最短路徑算法。

如果是無向，這是一棵樹，是微不足道的發現在樹上的最短路徑。如果你的圖是直接的，即使沒有循環，Dijkstra仍然不會工作，因爲它不適用於負邊緣圖。

在所有情況下，Dijkstra算法是算法爲您的問題一個可怕的選擇。

來源

2015-04-24 02:35:13

Dijkstra的負重算法

回答

相關問題