如何查找無向圖中兩個給定頂點之間的所有最短路徑？

Question

圖G是一個無向圖，其所有邊的權重相同。 u，v是2給定的頂點，如何找到O（| V |）中圖G中u和v之間最短路徑的個數？

| V |代表G中頂點的數量。

Answer 1

您可以使用BFS的計數變化。

這個想法是保存一個字典，它映射dict:(v,depth)->#paths（入口是頂點和當前深度，值是從源到具有所需深度的該頂點的路徑數）。

在BFS的每次迭代中，您都會跟蹤路徑的當前深度，並將找到的路徑的數量添加到下一級別。

，如果有3條路徑導致x和4點的路徑，導致y，無論在深度3，並且兩者都具有邊緣(x,u),(y,u)想法 - 然後有7條路徑導致u - 3導致x +（X ，u）和4導致y +（y，u）。

看起來應該是這樣的：

findNumPaths(s,t): 
    dict = {} //empty dictionary 
    dict[(s,0)] = 1 //empty path 
    queue <- new Queue() 
    queue.add((s,0)) 
    lastDepth = -1 
    while (!queue.isEmpty()) 
     (v,depth) = queue.pop() 
     if depth > lastDepth && (t,lastDepth) is in dict: //found all shortest paths 
      break 
     for each edge (v,u): 
      if (u,depth+1) is not entry in dict: 
       dict[(u,depth+1)] = 0 
       queue.push((u,depth+1)) //add u with depth+1 only once, no need for more! 
      dict[(u,depth+1)] = dict[(u,depth+1)] + dict[v,depth] 

     lastDepth = depth 
    return dic[t] 

運行時，如果使用哈希表詞典O（V + E）。

---

另一種解決方案（更容易編程但效率較低）爲：

1. Build the adjacency matrix of the graph, let it be `A`. 
2. Set `Curr = I` (identity matrix) 
3. while Curr[s][t] != 0: 
    3.1. Calculate Curr = Curr * A //matrix multiplication 
4. Return Curr[s][t] 

它工作的原因是(A^n)[x][y]是大小n的路徑在圖中A表示從x到y數。我們找到第一個高於零的數字，然後返回路徑的數量。