当前位置: 首页 > 知识库问答 >
问题:

稍微快一点的Bellman-Ford

於乐语
2023-03-14

我对贝尔曼-福特做了一点修改,这样它只能“有用”放松。也就是说,d(v)的松弛被更新了。

define Relax(u, v):
 if d(v) > d(u) + w(u,v)         //w(u,v) = weight of edge u->v
    d(v) = d(u) + w(u,v)


INIT // our usual initialization.
Queue Q
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q not empty)
{
  u ← Frontof(Q);
  for each neighbor v of u
  {
    Relax(u, v)

    if d(v) was updated by Relax and v not in the Q  //Here's where we're a bit smarter
        ADD v to End of Q.                           //since we add to Q if 
                                                     //the relaxation changed d(v)
  }
}

现在,如果所有最短路径最多有k条弧。那么最坏情况下的运行时是O(V*k),因为在这个智能版本中我们只经过k个弧。这比原来的O(V*E)快一点,因为| k|

有谁能告诉我一种图的类型,这种改进的版本并不比原来的Bellman-Ford算法好?也就是说,最佳情况下的性能是O(V*E)

共有1个答案

段劲
2023-03-14

考虑所有边都有负重的图。在该图中,如果顶点u有多条输入边,它将多次添加到Q。

声明|k|

 类似资料:
  • 嗨,我正在做一个游戏,我有一个问题。当球员落地时,他会稍微地下一点,例如: 我想要这样的东西: 这是我的重力代码: 谢谢

  • 我们知道bellman-ford算法检查每一步中的所有边,如果, d(v) 然后更新d(v),使得w(u,v)是边(u,v)的权重,d(u)是顶点的最佳查找路径长度。如果在一个步骤中我们没有顶点更新,那么算法将终止。在假设该算法的情况下,求出了图G中顶点

  • 我正在做一个有向图的项目,其中边的权重都依赖于变量x。我试图找到x的最小值,这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢,但我不明白如何——:我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在? 谢谢。

  • 我在试图理解这个算法是如何工作的。 给定一个问题,搜索从源s到图中所有顶点的路径, 我想我必须这样做: 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时?非常感谢。

  • 我如何在Bellman-Ford算法中证明这一点: 如果没有负权重循环,则从源到接收器的每个最短路径最多有边,其中是图中的顶点数。 有什么想法吗?

  • 我正在写一个JavaApplet使用JavaFX嵌入Swing。用户可以通过以下代码使用JFXPanel启动带有JavaFX组件的Swing GUI: 当Applet首先启动时,用户可以创建GUI元素并关闭它。以后他可以再创造。为此,我需要在内存中保存一个不可见的JFrame,其中包含一个JFXPanel的整个运行时,我从来没有使用过,因为我在某个地方读到,否则JavaFX应用程序线程会停止。现在