圖中最短路徑的數量

Question

我需要通過使用BFS來查找圖的兩個節點之間的所有路徑的數量。我想回答我的問題可以在這裏找到：

How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

但我不太明白。有人可以寫下算法，換句話說，我可以更好地理解它嗎？

Answer 1

假設你需要從src到dest。

每個頂點x關聯兩個值count和val，count是從src到x的最短路徑的數量，val是從src到x的最短距離。還維護一個訪問變量，告訴節點是否第一次到達。

應用通常的BFS算法，

Initialize u = src 
visited[u] = 1,val[u] = count[u] = 1 
For each child v of u, 
    if v is not visited 

的節點訪問第一次因此它具有從源只有一條路徑到現在經由u，高達V SO最短路徑是高達U 1條+最短路徑，以及數通過最短路徑達到v的方法與count [u]相同，因爲說你有5種方法可以從源頭到達，那麼只有這5種方法可以擴展到v，因爲v第一次遇到u，所以

val[v] = val[u]+1,  
count[v] = count[u], 
visited[v] = 1 

if v is visited 

如果v已經被訪問，這意味着有一些其他路徑通過其他v ertices，然後3案件出現了：

1 :if val[v] == val[u]+1 

如果當前VAL [V]，其通過一些其他路徑是DIST高達v等於VAL [U] 1，即，我們已就使用當前達到，其等於最短距離通過u的路徑和到v的另一個路徑，則到v的最短距離保持相同，但路徑的數量隨着到達u的路徑的數量而增加。

count[v] = count[v]+count[u] 

2: val[v] > val[u]+1 

如果到達的v的電流路徑比val的先前值的情況下[V]，則VAL [V]被存儲的電流路徑和Count [V]也被更新

val[v] = val[u]+1 
count[v] = count[u] 

第三情況是，如果當前路徑的距離大於以前的路徑，在這種情況下，不需要更改val [v]和count [v]的值。直到BFS完成後，執行此算法。 最後，val [dest]包含距離源的最短距離，count [dest]包含從src到dest的路數。