找到从给定节点 s 到任何其他节点 v 的最短路径数的算法？

Question

我想找到一种算法，当给定一个图 G=(V,E) 和一个来自 V 的节点 s 时，对于 V 中的任何节点 v 它找到从 s 到 v 的最短路径的数量。我了解到 BFS 算法找到从 s 到 v 的最短路径，但我只是不知道如何使用它来解决这个问题。任何帮助将不胜感激。

Answer 1

这是伪代码（意思是未经测试Python）。

path_count[s] = 1
length_to[s] = 0
todo = [s] # A queue
while len(todo):
    v = todo.pop(0)
    for w in edges(graph, v):
        if w not in length_to:
            length_to[w] = length_to[v] + 1
            path_count[w] = 0
            todo.append(w)

        if length_to[w] == length_to[v] + 1:
            path_count[w] += path_count[v]

之后length_to[v]给出到v的最短路径的长度，paths_to[v]给出到v的最短路径的数量。（这就是您要找的。）

找到从给定节点 s 到任何其他节点 v 的最短路径数的算法？

algorithm that finds the number of the shortest paths from given node s to any other node v?

algorithm

breadth-first-search