贝尔曼 - 福特：所有最短路径

1 回答

• 8

  如果你改变Bellman-Ford algorithm的第二步，你可以实现非常相似的东西：

  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 .

  回复于 2024-04-29T14:08:25+08:00