Dijkstra算法擴展了額外的限制變量

Question

我遇到了麻煩實現這個到我當前的路徑尋找算法。

目前我有Dijkstra書面和作品像它應該，但我需要走得更遠，並添加一個限制（範圍）。我可以更好地解釋一個圖像：

比方說，我有範圍。我想從A去E。我目前的算法，它應該如此，所以它的結果是A->B-E。

不過，我只需要與重量不超過所述範圍的路徑去 - ，這將意味着A->B->E是不是選項更多，但A->C->D->B->E（考慮對每一站的這個範圍/極限復位）

到目前爲止，我實現了一個名爲bool其中Possible將返回路徑的單一部件（例如A->B）是有可能比較我的極限/範圍。

我的主要問題是我不知道在哪裏/如何開始。我唯一的想法是看看Possible爲false（A->B，總路線爲A->B->E），並且從A到A->E再次運行算法，沒有/排除B stop/vertex。

這是一個很好的方法嗎？因爲我的大O符號會增加兩次（據我所知）。

Answer 1

我看到這樣

1. 創建一個新的圖G」只包含邊緣< 80的兩種方式，並查找存在的最短路徑...還原時間O(V+E)，和額外的O(V+E)內存使用

2. 您可以更改Dijkstra算法，忽略邊緣> 80，只跳過邊緣> 80，給值鄰居頂點的時候，複雜性和內存使用情況將保持在同一這種情況下

Answer 2

創建圖表的一個臨時版本，並設定高於閾值到無窮大的所有的權重。然後運行普通的Dijkstra算法。

複雜性會增加與否，取決於你的算法的版本：

• ，如果你有O(V^2)那麼將增加至O(E + V^2)
• 如果你有O(ElogV)版本，那麼將增加至O(E + ElogV)
• 如果您有O(E + VlogV)版本，它將保持不變

正如ArsenMkrt所指出的那樣，您可以刪除這些邊緣，這更加有意義，但會使複雜性變得更糟。儘管修改算法以跳過這些邊緣似乎是最佳選擇，正如他在his answer中所建議的那樣。