我已经成功地实现了Bellman-Ford,当边具有负权重/距离时,找到最短路径的距离。我无法让它返回所有最短路径(当最短路径有联系时)。我设法用Dijkstra获得所有最短的路径(给定的一对节点之间)。贝尔曼-福特有可能吗?(只是想知道我是否在浪费时间)
如果你稍微改变一下Bellman-Ford算法的第二步,你可以得到类似的结果:
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.preference
是顶点列表。如果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.id)
以便打印所有路径。
注意:如果在算法完成后删除重复元素,则可以从修改后的算法中排除,如果u不在v.predecessorv.predecessor=u
。
我知道Bellman-Ford算法最多需要| V |-1次迭代才能找到最短路径,如果图不包含负权重循环。有没有办法修改Bellman-Ford算法,使其在1次迭代中找到最短路径?
我这里有一个更聪明的贝尔曼福特版本: 有人能想到一种图,对于这种图,该算法的时间复杂度下限为(V*E),其中V=#顶点,E=#边 我想看看这个陷阱在哪里。
我有一个家庭作业来实现贝尔曼·福特的算法,并在一些图形上测试它。我实现了这个算法,在3张图中的2张上测试了它,它是有效的。但是在第三个图中,我在调用函数时没有输出。 此部分创建图形及其边。函数将顶点数和边数作为参数。 这是添加新边的函数。 下面是我对Bellman Ford算法的实现。
我正在努力改进Bellman-Ford算法的性能,我想知道改进是否正确。 我运行松弛部分不是V-1而是V次,并且我得到了一个涉及的布尔变量,如果在外循环的迭代过程中发生任何松弛,则将其设置为。如果在n.迭代中没有发生松弛,其中n 我认为这可能会改善运行时,因为有时我们不必迭代V-1次来找到最短路径,而且我们可以更早地返回,而且它也比用另一块代码检查循环更优雅。
在具有V节点和E边的有向图中,Bellman-Ford算法将每个顶点(或者更确切地说,每个顶点的边)松弛(V-1)次。这是因为从源到任何其他节点的最短路径最多包含(V-1)条边。在第V次迭代中,如果边可以松弛,则表示存在负循环。 现在,我需要找到被这个负循环“摧毁”的其他节点。也就是说,由于从源到位于负循环中的节点的路径上有一个或多个节点,因此一些不在负循环中的节点现在与源的距离为负无穷远。 实现
我一直试图通过以下资源来理解贝尔曼福特的正确实现:1 如果我们已经知道给定的加权有向图不包含一个圈(因此也没有负圈),是否遵循Bellman-Ford算法的正确实现? 我在上述实现中遇到的第一个问题是,如果图中只有两个节点具有从源节点到目标节点的定向边,那么需要修改for的第一个