алгоритм, который находит количество кратчайших путей от данного узла s к любому другому узлу v?

Question

Я хочу найти алгоритм, который при задании графа G = (V, E) и узла s из V для любого узла 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. (Что вы и искали.)