Bellman-Ford算法：所有最短路径

Question

Bellman-Ford算法：所有最短路径

6

我已经成功地实现了Bellman-Ford算法来查找具有负权重/距离的边的最短路径距离。但是，我无法让它返回所有最短路径（当最短路径存在并列情况时）。我使用Dijkstra算法成功地获得了所有最短路径（在给定节点对之间）。Bellman-Ford算法能否实现这一点？（只是想知道我是否在浪费时间尝试）

- user1507844

从数学上讲，我不确定这是可能的。例如，如果所有边的成本都为零，那么您可以采取无限多个可能的最短路径。您想要最短无环路径吗？ - templatetypedef

是的，抱歉，我应该说明一下。我想找到两个节点之间所有最短无环路径。 - user1507844

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zeta · Accepted Answer

如果你稍微修改贝尔曼-福特算法的第二步，你可以实现非常相似的效果：

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

       if u.distance == INFINITY:
           // skip start nodes that have no valid path from source yet
           continue

       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从修改的算法中排除。