Беллман-Форд: все кратчайшие пути

Question

Я успешно реализовал Bellman-Ford, чтобы найти расстояние по кратчайшему пути, когда ребра имеют отрицательные веса / расстояния. Я не смог заставить его возвращать все кратчайшие пути (когда есть связи для кратчайших). Мне удалось получить все кратчайшие пути (между данной парой узлов) с Dijkstra. Это возможно с Bellman-Ford? (просто хочу знать, трачу ли я свое время на попытки)

Answer 1

Если вы немного измените второй шаг алгоритма Беллмана-Форда, вы сможете достичь чего-то очень похожего:

for i from 1 to size(vertices)-1:
   for each edge uv in edges: // uv is the edge from u to v
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           v.distance := u.distance + uv.weight
           v.predecessor[] := u
       else if u.distance + uv.weight == v.distance:
           if u not in v.predecessor:
               v.predecessor += u

где v.predecessor это список вершин. Если новое расстояние v равно пути, который еще не включен, включая нового предшественника.

Чтобы распечатать все кратчайшие пути, вы можете использовать что-то вроде

procedure printPaths(vertex current, vertex start, list used, string path):
    if current == start:
        print start.id + " -> " + path
    else:
        for each edge ve in current.predecessors:
            if ve.start not in used:
                printPaths(ve.start,start, used + ve.start, ve.start.id + " -> " + path)

использование printPaths(stop,start,stop,stop.id) для того, чтобы напечатать все пути.

Примечание: можно исключить if u not in v.predecessor then v.predecessor += u из модифицированного алгоритма, если вы удалите дубликаты элементов после завершения алгоритма.