在有向未加权图中查找两个节点之间的所有最短路径的数量
Finding the number of all the shortest paths between two nodes in directed unweighted graph
我需要帮助来找出有向未加权图中两个节点之间的所有最短路径的数量。
我可以使用 BFS 算法找到最短路径之一，但我不知道如何找到所有最短路径。
知道我可以使用的算法/伪代码吗？
谢谢！！
修改广度优先搜索以继续搜索，直到它开始找到更长的路径，而不是停止并仅返回第一个路径。
我想到的第一个想法是下一个：
让我们将起始顶点命名为 s，将结束顶点命名为 e。
我们可以存储两个数组：D和Q。 D[i]是从s到i的最短路径长度，Q[i]是s到i之间的最短路径数。
我们如何重新计算这些数组？
首先，让我们设置D[s] = 0和Q[s] = 1。然后我们可以使用 well-known 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]。
您可以记住有多少条路径通向每个节点，并在发现新节点时总结该数字。
为简单起见，我们假设您有常规 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。
这基本上是一个地图（或二维矩阵），它的键是一对顶点和一个整数 - 距离，它的值是从源头到那个顶点的最短路径的数量，距离 k.
很容易看出对于每个顶点v:
d[v,k] = sum { d[u,k-1] | for all edges (u,v) }
d[source,0] = 0
现在，您可以轻松找到通向每个节点的长度为 k 的最短路径的数量。
优化：
可以看到"number of shortest paths of length k"是多余的，实际上每个顶点只需要一个k的值。这需要一些 book-keeping，但可以节省一些 space。
祝你好运！
我需要帮助来找出有向未加权图中两个节点之间的所有最短路径的数量。
我可以使用 BFS 算法找到最短路径之一，但我不知道如何找到所有最短路径。
知道我可以使用的算法/伪代码吗？
谢谢！！
修改广度优先搜索以继续搜索，直到它开始找到更长的路径，而不是停止并仅返回第一个路径。
我想到的第一个想法是下一个：
让我们将起始顶点命名为 s，将结束顶点命名为 e。
我们可以存储两个数组：D和Q。 D[i]是从s到i的最短路径长度，Q[i]是s到i之间的最短路径数。
我们如何重新计算这些数组？
首先，让我们设置D[s] = 0和Q[s] = 1。然后我们可以使用 well-known 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]。
您可以记住有多少条路径通向每个节点，并在发现新节点时总结该数字。
为简单起见，我们假设您有常规 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。
这基本上是一个地图（或二维矩阵），它的键是一对顶点和一个整数 - 距离，它的值是从源头到那个顶点的最短路径的数量，距离 k.
很容易看出对于每个顶点v:
d[v,k] = sum { d[u,k-1] | for all edges (u,v) }
d[source,0] = 0
现在，您可以轻松找到通向每个节点的长度为 k 的最短路径的数量。
优化：
可以看到"number of shortest paths of length k"是多余的，实际上每个顶点只需要一个k的值。这需要一些 book-keeping，但可以节省一些 space。
祝你好运！