如何限制最短路徑 - dijkstra算法的最大代價？

Question

我想知道如何爲最短路徑問題分配最大成本值。在我的問題中，我有與節點相關的風險。所以我想盡量減少風險，但儘管如此，我希望它找到一個節點數量有限的解決方案（例如，找到節點A到節點B的最小風險，同時確保解決方案不超過n個節點）。很多。

Answer 1

Dijkstra算法最好先搜索，即我們應該肯定的是，以最好的節點的距離永遠不會變得更好。它適用於具有非負邊的最小Dijkstra。在一般情況下，您可以使用Ford-Bellman。如果你想使用不超過n個頂點，我可以建議你採用動態規劃DP [頂] [used_vertex_count]與複雜度爲O（| V | * n）的狀態和內存和O（| E | * n）的時間。或者創建圖形的鄰接矩陣，其中主對角線上的零點和缺少邊緣的無窮遠點並計算它的n指數。 a_ {ij}將使用不超過n個頂點從i到j的最小路徑。

Answer 2

我認爲一些算法，包括啓發式會得到更好的適合這裏，啓發式是如何「接近」你是在每一步的目標的一個概念，哪個節點將帶你更接近球門。如果沒有這些，我認爲我們需要在最壞的情況下運行一個指數算法（當只使用n節點無法達到目標時，我們會在所有使用n節點的路徑之前得出結論該問題無法解決）。

使用非啓發式算法的一個例子是：以常規方式運行Dijkstra's，選擇最小風險的節點。一路上，跟蹤您訪問過的節點數量。如果節點數超過n，則放棄當前路由並回溯到前一個節點，並使用具有次低風險的節點。當然，你不能僅僅回溯到n以上的一個等級，因爲如果目標是在下一個等級中的話，它就會被挑選出來。因此，你回到n-2水平並繼續。這也將是指數性的，因爲沒有檢查所有路徑來確定不存在的真實方式。

這也可能是我想的東西。

Answer 3

你想用Prim算法，因爲它發現在給定的圖全部最小生成樹。然後很容易選擇具有所需約束的mst。