algorithm - 在有向未加权图中查找两个节点之间的所有最短路径的数量

Question

我需要帮助来找出有向未加权图中两个节点之间的所有最短路径的数量。

我能够使用 BFS 算法找到最短路径之一，但我不知道如何找到所有最短路径。

知道我可以使用的算法/伪代码吗？

谢谢!!

Answer 1

您可以记住有多少条路径通向每个节点，并在发现新节点时总结该数字。

为简单起见，我们假设您有常规 BFS 算法，每当您使用边 (u,v) 时，都会调用 visit(u,v,k)，其中:

u - the source node of the edge
v - the target node of the edge
k - the distance from the original source to u

除此之外，假设您有一个映射 d:(vertex,distance)->#paths。
这基本上是一个 map (或二维矩阵)，它的键是一对顶点和一个整数 - 距离，它的值是从源头到那个顶点的最短路径的数量，距离 k.

很容易看出对于每个顶点v:

d[v,k] = sum { d[u,k-1] | for all edges (u,v) } 
d[source,0] = 0

现在，您可以轻松找到通向每个节点的长度为 k 的最短路径的数量。

优化:

您可以看到“长度为 k 的最短路径数”是多余的，实际上每个顶点只需要 k 的一个值。这需要一些簿记，但可以节省一些空间。

祝你好运!