2

我在这里有一个更智能的 Bellman-Ford 版本：

    //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 = #vertices, E = #edges

我想看看这其中的陷阱在哪里。

4

3 回答 3

3

自从我上次考虑短路径算法以来已经有好几年了，如果我忘记了什么，请纠正我。

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

假设您访问了一个完整的图表。从第一个节点开始，您将排队 V-1 个节点，因为所有节点都是 s 的邻居。假设您不走运，并且您排队的最后一个节点是到所有节点的最短路径的一部分。因此，您将不得不排队 V-2 节点（所有节点，减去源节点和您正在评估的节点......）。现在让我们非常不走运，假设您排队的最后一个节点再次成为所有剩余节点的路径的一部分......您必须排队 V-3 节点，等等。

因此，如果一切都出错了，您将评估 V-1*V-2*...*3*2*1 节点。您应该很容易找出这与 |E| 的总和。

对于每个节点，你在做什么？检查它的每个邻居。每个节点都有 V-1 个邻居。

对于您的算法，我们已经处于 O(|V-1| |E|) 最坏情况复杂度。如果我没记错的话，Bellman-Ford 算法会检查每条边以确保没有负权循环，你也应该这样做；并且将 1 添加到 V-1，也就是 (|V| |E|) 最坏情况复杂度。

于 2012-05-21T13:29:52.313 回答
0

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

于 2012-05-21T05:38:15.180 回答
0

这是福特-贝尔曼的一个改进。它的实施速度比平时快。当然，在最坏的情况下，时间复杂度可能是 O(nm)。但是，很难创建一个输入来破解这个算法。在比赛中，带队列的福特-贝尔曼比 Dijkstra 执行得更快。但是，您必须创建一个数组调用 Inqueue 来检查当前元素是否在队列中：

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];
于 2013-09-03T08:52:10.090 回答