有向圖中得分最高的計算路徑

Question

我有一個有向圖，每個節點都有一個分數。從節點開始，我需要找到通過遵循路徑可以實現的最高分數。並非所有節點都可以成爲最終節點。也可以重新訪問一個節點，但只有第一次訪問纔算得分。我如何計算最高可達分數？

Answer 1

首先，您可能會發現該圖的strongly connected components。然後你可以建立一個濃度的圖。

在縮合每個頂點可具有等於在初始圖頂點的分數的總和的分數。

藍數字顯示在初始圖中每個頂點的得分。黃色 - 在圖中凝結。

如果它們包含最後一個節點，還要標記一些冷凝的頂點作爲終端。您還可以將每個圖頂點映射到冷凝中的頂點。

連接組件的概念很重要，因爲如果您發現自己位於組件的一個頂點中，則可以輕鬆訪問組件的所有其他頂點以最大化分數。您可以自由地重新訪問任何次數的每個頂點。

冷凝本身是一個有向非循環圖。現在可以遍歷與深度優先搜索的縮合圖表維持功能

˚F _v = 0 - 如果V沒有到達終止頂點（上下面畫面右下頂點）

˚F _v = MAX _我（F _{子 v，I}）+得分 _v - 否則

紅色圓圈顯示在初始圖和冷凝認爲終端是什麼頂點。 綠色的數字顯示凝結圖中每個頂點的F值。

對於你的問題的答案是在初始圖中對應於起始頂點的凝結頂點的F值。總的時間複雜度爲O（N + M），其中N是頂點數，M是初始圖中的邊數。