Dijkstra的最短路徑算法是行不通的

我有正邊權和積極的節點的權重曲線。路徑的長度被定義爲沿路徑的所有邊權重加上路徑上遇到的最大節點權重的總和。Dijkstra的最短路徑算法是行不通的

我想最初以爲一個改進Dijkstra會的工作，但我發現一個測試情況下，它會失敗。我應該如何解決這個問題？有什麼標準算法我應該看看？

我改進Dijkstra如下：在每個節點我記錄的最短路徑，到目前爲止，還最大節點重量至今我所看到的，並用它來計算長度到鄰近節點。請參閱我的評論的細節。

下面是Dijkstra失敗的圖表： http://i.imgur.com/FQhRzXV.jpg 綠色的數字是節點標籤。藍色的一切都是權重（節點和邊權重）。假設我想計算節點1和7之間的最短路徑（用綠色標記）。 Dijkstra的問題在於節點4總是記錄路徑1-8-9-4，因爲它比路徑1-2-3-4（前者長度9與後者長度13）短。但是要到達節點7，路徑1-8-9-4-5-6-7比1-2-3-4-5-6-7長。

來源

2013-09-21 elexhobby

那你試試？爲什麼失敗？我很確定修改後的Dijkstra會工作:-) –

修復啓動節點。對於每個鄰居，存儲一對數字（到該鄰居的最短路徑，即該路徑上迄今爲止遇到的最大節點權重）。將它們放入隊列並選擇具有最短路徑的節點。繼續。在添加新節點B連接到被訪問的節點的，如果重量上路徑中遇到B'最大節點權重的到節點A，B上的一對是（到+邊緣重量AB遇到直到一個，最多節點的最短路徑）。否則，b上的對是（最短路徑到最大節點直到a +節點b的權重+邊權重ab，節點b的權重）。 – elexhobby

我認爲你解決了「總重量最小的路徑，並追蹤了該路徑上最大的加權邊緣」。我認爲問題可能是要求「最小（總重量加最大重量）的路徑」。簡單地跟蹤最大的重量並不能解決這個問題。 – DanielV

如果你能原諒一個爲了更大多項式時間，那麼很容易算法：

ModifiedShortestPath(u, v, G) { 
    X = StandardardShorestPath(u, v, G); 
    E = heaviest edge in X 
    F = all edges in G of weight >= E 
    Y = ModifiedShortestPath(u, v, G - F); // recur here on G without the F edges 
    return Min(X, Y); 
}

這是運行| E |比標準最短路徑多了一倍。

來源

2013-09-21 20:08:57 DanielV

Dijkstra的最短路徑算法是行不通的

回答

相關問題