改進的Dijkstra算法

Question

我們給出了一個有向圖，其邊緣權重W介於0和1之間。從源到目標節點的路徑成本是位於從源到目標節點的路徑上的邊的權重的乘積。我想知道一個算法，它可以找到多項式時間的最小代價路徑或使用任何其他啓發式。

我認爲沿着邊緣權值（取mod值）的對數值，然後對這個圖應用dijkstra，但認爲會出現無法計算的精度問題。

有沒有其他更好的方法，或者我可以改進日誌方法。

Answer 1

在Dijkstra算法中，當你訪問一個節點時，你知道這個節點沒有更短的路。如果你用0..1之間的權重乘以邊，就好像你訪問更多的頂點，你會得到更小的數。

基本上這相當於找到圖中最長的路徑。這也可以通過使用取對數的想法來看到，因爲0和1之間的數字的對數是負數。如果您取權重對數的絕對值，則最長路徑對應於乘法圖中的最短路徑。

如果您的圖是非循環的，則有一個簡單的算法（從Longest path problem修改）。

1. 查找DAG的拓撲排序。
2. 對於每個頂點，您需要存儲路徑的開銷。初始化爲一個。
3. 從開始頂點開始按照拓撲順序遍歷DAG。在每個頂點檢查所有的孩子，如果成本比以前小，更新它。以最低的成本存儲您到達此頂點的頂點。

在到達最終頂點後，您可以使用存儲的頂點從末端頂點返回，找到「最短」路徑。

當然，如果圖形不是非循環的，您可以通過無限重複循環來始終達到零終端成本。