查找圖中每個節點最多有兩個輸入邊和兩個輸出邊的最長路徑

Question

由於標題說我必須在有向圖中找到最長路徑，其中每個節點最多有兩個輸入邊和兩個輸出邊。我不知道這個事實是否有助於任何事情。圖表最多有10000個節點。我需要找到從節點0到節點'Exit'的10001的最長路徑。

我試圖編碼dijkstra，但它沒有工作。

在此先感謝。

Answer 1

您可以預處理您的圖形，並將邊緣權重設置爲非常高的值，以連接到違反規則的節點的邊緣，然後使用返回最長路徑的修改版本的dijkstra。