計算每個節點的有向圖中特定節點可以達到的節點數量

Question

在有向圖中（假設它有很多週期），我需要計算每個節點可以通過特定節點達到的節點數量節點。我怎樣才能以最小的努力做到這一點？我需要使用哪種算法？

注意：我認爲這個問題的一個合理的算法應該遞歸地計算這個數字（比如'a節點'的結果取決於'節點b'的結果，如果a連接到b）。

Answer 1

您正在尋找的算法被稱爲Floyd-Warshall algorithm，這是一個非常好的高效動態編程算法。它可用於計算圖中每個單獨節點可到達的節點集（transitive closure），但它更常用於計算從圖中每個單獨節點到所有其他節點的最短路徑。 （編輯：Floyd-Warshall算法比你需要的算法更加複雜，因爲它已經被Floyd擴展來計算最短路徑，你可能會發現this page有幫助，它只描述了「Warshall」算法的一部分 - 你需要的部分。）

我碰巧正在研究它現在上課，並在我的桌子上有紙。對於FW的傳遞閉包的版本復發是：

T(i,j,k) = T(i,j,k-1) ∨ (T(i,k,k-1) ∧ T(k,j,k-1)) 

哪裏T(a,b,c)是真的，當且僅當有從A到B的曲線僅使用第一個C頂點（你必須給他們一個任意的路徑在運行算法之前編號）。

直觀，復發說，有一個從i到j使用第k個頂點的路徑，如果：

• 有i和j之間的直接路徑，使用前k-1頂點或
• 我和k之間有一條路徑，而k和j之間有一條路徑，使用第一個k-1頂點。

您可以使用典型的動態編程方式構建T（i，j，k）的整個三維表，然後計算所需的源節點上的所有TRUE條目（使用max k），以獲得該源節點的傳遞閉包的大小。

如果你還在下面我可憐的解釋，你可以使算法有一些技巧非常有效的：

• 事實證明，你不需要在你的表中的K尺寸;你可以重複覆蓋同一行值。現在，該計劃將是這樣的：

  T(i,j) = T(i,j) || (T(i,k) && T(k,j))

• 如果T（I，K）爲0，那麼你可以跳過整個事情，因爲什麼都不會在這一步改變。

• 如果T（i，k）是1，那麼新值將只是T(i,j) || T(k,j)。這可以用大塊完成，因爲現代處理器上的塊OR非常快。

希望幫助...