贝尔曼福特变奏曲

Question

我这里有一个更聪明的贝尔曼福特版本：

    //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=#边

我想看看这个陷阱在哪里。

Answer 1

这对福特贝尔曼来说是一个进步。它比正常情况下执行得更快。当然，在最坏的情况下，时间复杂度可以是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];

Answer 2

我不确定这是否有效，但是假设它有效，你可以创建一个高炉没有改进的情况。创建开始和结束节点，并在两者之间放置连接两者的N个顶点。算法仍然必须考虑每条路径。

Answer 3

自从我上次想到短路径算法已经好几年了，如果我忘了什么，请纠正我。

首先，我们将首先排除负加权周期情况，但它可能是最坏情况性能的来源。

让我们假设您访问一个完整的图形。从第一个节点开始，您将排队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 |）最坏情况的复杂性。