計算有向圖中任意兩個節點之間的節點 - 不相交路徑的數量，使得距離<= K

Question

我們如何統計任意兩個節點之間的節點 - 不相交路徑的數量，使得兩個節點之間的距離最大K ？

有關節點 - 不相交路徑的詳細信息可以是found here。

我們給出一個有向圖，其中我們必須計數節點的數目 - 從頂點u不相交路徑v使得它們之間的節點的最大數目爲K - 2（u和v從ķ遞減，因此K-2）。圖中頂點的數量可以高達10^5並且邊緣可以是6 * 10^5。我想爲每個節點實施BFS，直到距離源節點的最大距離小於K。但我沒有得到實施的想法。有人請幫助我嗎？

如果有人有想法使用DFS解決它，請分享它。

Answer 1

DFS是解決此類問題的關鍵。我們可以使用DFS輕鬆枚舉兩個頂點之間的所有可能路徑，但是我們必須注意距離約束的。

我的算法將遍歷的邊數視爲約束條件。您可以輕鬆將其轉換爲遍歷的節點數。以此作爲練習。

我們記錄變量e所遍歷的邊的數量。如果e變得大於K - 2，我們終止遞歸調用DFS。我們保留boolean數組visited。但是如果遞歸調用在沒有找到成功路徑的情況下終止，我們會放棄對數組visited所做的任何更改。

只有當遞歸調用DFS成功找到路徑時，我們纔會爲程序的其餘部分保留visited數組。

所以對於算法的僞代碼將是：

main function() 
{ 
visited[source] = 1  
e = 0//edges traversed so far. 
sum = 0// the answer 
found = false// found a path. 
dfs(source,e) 
print sum 
. 
. 
. 
} 

dfs(source,e) 
{ 
if(e > max_distance) 
{  
    return 
} 

if(e <= max_distance and v == destination) 
{ 
    found = true 
    sum++  
    return 
} 

for all unvisited neighbouring vertices X of v 
{ 
    if(found and v != source) 
    return; 
    if(found and v == source) 
    { 
    found = false 
    visited[destination] = 0 
    } 

    visited[X] = 1 
    dfs(X , e + 1) 
    if(!found) 
    visited[X] = 1 
} 

}