需要檢測圖形中具有最小權重的結束路徑

想要找到從節點a到任何節點的最短加權路徑。沒有給出目標節點。人們可以多次訪問任何頂點。需要檢測圖形中具有最小權重的結束路徑

如果路徑重的應小於Integer.MAX

什麼是算法進行..？不能檢測算法本身。

我嘗試過旅行商問題，但它不匹配;無論它匹配的Dijkstra ...

如何在內存中保存的所有路徑是這裏的主要挑戰..

編輯：圖形不針對一個，有沒有負面wieghts。

你是圖形定向的還是無定向的？它可以有周期嗎？邊緣權重是正面的，負面的還是兩者都可以？ – hgazibara 2015-04-05 06:26:44

對於無向圖無負權，它可以使用Floyd-Warshall算法來找出所有對隨時間複雜度O最短路徑（V^3），其中V是頂點數量。該算法還允許一個簡單的方法來reconstruct the all computed shortest paths。它使用O（V^2）內存來存儲距離和重建路徑的附加信息。

也有一些other algorithms解決這個問題具有更好的時間複雜性，但Floyd-Warshall真的很容易編碼和開始。

2015-04-05 06:39:08 hgazibara

想找到從節點a到任何節點的最短加權路徑。

我立即想到Dijkstra's algorithm，因爲這正是它所做的。

如何保存在內存中的所有路徑是這裏的主要挑戰..

對於圖中的每個節點，跟蹤這將導致最短路徑前一個節點。看看pseudocode，第20行。

要構建路徑，只需從目標節點向後走，直到到達源節點。

2015-04-06 14:38:45 j449li

回答