如何在无向图中找到两个给定顶点之间的所有最短路径？

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]中大小路径的数量表示从到。我们找到第一个大于零的数字，并返回路径数。nAxy