多個目的地的最高加權路徑

Question

我有一個有向循環加權圖。我想找到一個權重最高的路徑，X個頂點的長度，我不在乎目的地是什麼。我只想找到最高的成本。

Answer 1

這可以通過動態編程類算法來解決。

由於您只有幾百個節點，並且X的輪數爲10.您可以爲每個節點分配一個大小爲X的數組Fv，而Fv [i]表示從源節點到節點v的最大開銷長度i。

讓我們來源。設置Fs [0] = 0，並且所有其他Fs [i] = - 無窮大。

所有其他陣列初始化爲-infinity數組。

現在，

爲每個節點V，執行以下更新：

的Fv [I] = MAX {的Fv [I]，FW [I-1] +成本（W，V ）|其中w爲v的鄰居}

重複上面的至少X次的更新，然後檢查的Fv [X]所有v到得到你想要的最大值。

您可以使用一些額外的信息來檢索路徑，這應該很容易做到。

以上算法是Bellman-Ford Algorithm的特殊情況

Answer 2

您可以使用Bellman-Ford algorithm來做你想做的。