我这里有一个更聪明的贝尔曼福特版本:
//Queue Q; source s; vertices u, v
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q !empty)
{
u ← Dequeue(Q)
for each neighbor v of u
{
Relax(u, v)
if d(v) was updated by Relax and v not in Q
Enqueue(v)
}
}
有人能想到一种图,对于这种图,该算法的时间复杂度下限为(V*E),其中V=#顶点,E=#边
我想看看这个陷阱在哪里。
这对福特贝尔曼来说是一个进步。它比正常情况下执行得更快。当然,在最坏的情况下,时间复杂度可以是O(n.m)。但是,很难创建一个输入来破解这个算法。在比赛中,排队的福特行李员比迪克斯特拉执行得更快。但是,必须在队列中创建数组调用,以检查当前元素是否在队列中:
qu : queue;
inqueue : array of bool;
for i in [1..n] do { d[i]=oo; inqueue[i]=false; }
qu.push(start);
d[start] = 0;
repeat
u=qu.pop;
inqueue[u]=false;
for v in adj[u] do
if minimize(d[v], d[u]+uv) then
if !inqueue[v] then
{ inqueue[v] = true; qu.push(v); }
until qu.empty;
print d[target];
我不确定这是否有效,但是假设它有效,你可以创建一个高炉没有改进的情况。创建开始和结束节点,并在两者之间放置连接两者的N个顶点。算法仍然必须考虑每条路径。
自从我上次想到短路径算法已经好几年了,如果我忘了什么,请纠正我。
首先,我们将首先排除负加权周期情况,但它可能是最坏情况性能的来源。
让我们假设您访问一个完整的图形。从第一个节点开始,您将排队V-1节点,因为所有节点都是s的邻居。假设您运气不好,并且您排队的最后一个节点是到所有节点的最短路径的一部分。因此,您必须将V-2节点排队(所有节点,减去源节点和您正在计算的节点…)。现在让我们非常不走运,假设您排队的最后一个节点也是所有剩余节点路径的一部分。。。您必须排队等待V-3节点,等等。
因此,如果一切都出了问题,您将评估V-1*V-2**3*2*1个节点。你应该很容易地找到这是如何加起来的。
对于每个节点,您都在做什么?检查每个邻居。每个节点都有V-1个邻居。
对于您的算法,我们已经达到了O(| V-1 | | E |)最坏情况复杂度。如果我记得清楚的话,Bellman-Ford算法检查每条边以确保没有负加权循环,你也应该这样做;这给V-1增加了1,也就是(| V | | E |)最坏情况的复杂性。
我知道Bellman-Ford算法最多需要| V |-1次迭代才能找到最短路径,如果图不包含负权重循环。有没有办法修改Bellman-Ford算法,使其在1次迭代中找到最短路径?
我有一个家庭作业来实现贝尔曼·福特的算法,并在一些图形上测试它。我实现了这个算法,在3张图中的2张上测试了它,它是有效的。但是在第三个图中,我在调用函数时没有输出。 此部分创建图形及其边。函数将顶点数和边数作为参数。 这是添加新边的函数。 下面是我对Bellman Ford算法的实现。
在具有V节点和E边的有向图中,Bellman-Ford算法将每个顶点(或者更确切地说,每个顶点的边)松弛(V-1)次。这是因为从源到任何其他节点的最短路径最多包含(V-1)条边。在第V次迭代中,如果边可以松弛,则表示存在负循环。 现在,我需要找到被这个负循环“摧毁”的其他节点。也就是说,由于从源到位于负循环中的节点的路径上有一个或多个节点,因此一些不在负循环中的节点现在与源的距离为负无穷远。 实现
经过大量谷歌搜索,我发现大多数消息来源说迪克斯特拉算法比贝尔曼-福特算法“更有效”。但是在什么情况下Bellman-Ford算法比Dijkstra算法更好呢? 我知道“更好”是一个宽泛的说法,所以具体来说,我指的是速度和空间,如果适用的话。当然,在某些情况下,贝尔曼-福特方法比迪克斯特拉方法更好。
我一直试图通过以下资源来理解贝尔曼福特的正确实现:1 如果我们已经知道给定的加权有向图不包含一个圈(因此也没有负圈),是否遵循Bellman-Ford算法的正确实现? 我在上述实现中遇到的第一个问题是,如果图中只有两个节点具有从源节点到目标节点的定向边,那么需要修改for的第一个
我正在努力改进Bellman-Ford算法的性能,我想知道改进是否正确。 我运行松弛部分不是V-1而是V次,并且我得到了一个涉及的布尔变量,如果在外循环的迭代过程中发生任何松弛,则将其设置为。如果在n.迭代中没有发生松弛,其中n 我认为这可能会改善运行时,因为有时我们不必迭代V-1次来找到最短路径,而且我们可以更早地返回,而且它也比用另一块代码检查循环更优雅。