贝尔曼 - 福特：所有的最短路径 [英] Bellman-Ford: all shortest paths

问题描述

我已经成功地实现贝尔曼 - 福特找到最短路径的距离时，边缘有负权重/距离。我没有能够得到它返回所有的最短路径（当有联系的最短）。我设法让所有的最短路径与Dijkstra算法（给定的对节点之间）。与贝尔曼 - 福特这可能吗？ （只是想知道如果我在浪费时间尝试）

I've successfully implemented Bellman-Ford to find the distance of the shortest path when edges have negative weights/distances. I've not been able to get it to return all shortest paths (when there are ties for shortest). I managed to get all shortest paths (between a given pair of nodes) with Dijkstra. Is this possible with Bellman-Ford? (just want to know if I'm wasting my time trying)

推荐答案

如果你改变的 Bellman-Ford算法​​一点点就可以实现的东西非常相似：

If you alter the second step of the Bellman-Ford algorithm a little bit you can achieve something very similar:

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

其中，诉predecessor ​​是顶点的列表。如果新的距离为V 等于它不包括尚未包括新的predecessor的路径。

where v.predecessor is a list of vertices. If the new distance of v equals a path which isn't included yet include the new predecessor.

为了打印您可以使用类似

In order to print all shortest paths you could use something like

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.id）以打印所有路径。

注：可以排除如果u在V predecessor则v predecessor ​​+ = U 从改进算法，如果你删除。之后，该算法已经完成重复的元素。

Note: It is possible to exclude if u not in v.predecessor then v.predecessor += u from the modified algorithm if you remove duplicate elements after the algorithm has finished.

这篇关于贝尔曼 - 福特：所有的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！