我需要帮助来查找有向未加权图中两个节点之间所有最短路径的数量。
我能够使用 BFS 算法找到最短路径之一，但我不知道如何找到所有最短路径。
对我可以使用的算法/伪代码有任何想法吗？
谢谢！！
您可以通过记住通向每个节点的路径数量来做到这一点，并在发现新节点时汇总该数字。
为简单起见，假设您有常规的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。
这基本上是一个地图（或 2D 矩阵），它的关键是一对顶点和一个整数 - 距离，它的值是从源到该顶点的最短路径数，距离k。
很容易看出，对于每个顶点 v：
d[v,k] = sum { d[u,k-1] | for all edges (u,v) }
d[source,0] = 0
现在，您可以轻松找到通向每个节点的最短路径数k长度。
优化：
您可以看到"长度为 k 的最短路径数"是多余的，实际上每个顶点只需要一个 k 值。这需要一些簿记，但可以节省一些空间。
祝你好运！
我想到的第一个想法是下一个：
我们将开始顶点命名为 s，将结束顶点命名为 e 。
我们可以存储两个数组： D 和 Q . D[i]是从s到i的最短路径的长度，Q[i]是s和i之间的许多最短路径。
我们如何重新计算这些数组？
首先，让我们设置D[s] = 0和Q[s] = 1。那么我们可以使用众所周知的bfs：
while queue with vertexes is not empty
get v from queue
set v as visited
for all u, there's an edge from v to u
if u is not visited yet
D[u] = D[v] + 1
Q[u] = Q[v]
push u into the queue
else if D[v] + 1 == D[u]
Q[u] += Q[v]
答案是Q[e].
修改您的广度第一次搜索以继续，直到它开始找到更长的路径，而不是停止并只返回第一个路径。