为什么 D'Esopo-Pape 算法具有最坏情况指数时间复杂度？

Question

D'Escopo-Pape 算法在实现上与 Dijkstra 算法非常相似，并且适用于负权重边缘，但不适用于负循环。在大多数情况下，它显然比 Dijkstra 算法和 Bellman-Ford 算法更快。 但显然在特殊情况下，该算法需要指数时间。

有人可以提供一些例子或给我指出一些更彻底地分析该算法的材料吗？

这是实现：

struct Edge {
    int to, w;
};

int n;
vector<vector<Edge>> adj;

const int INF = 1e9;

void shortest_paths(int v0, vector<int>& d, vector<int>& p) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<int> m(n, 2);
    deque<int> q;
    q.push_back(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        m[u] = 0;
        for (Edge e : adj[u]) {
            if (d[e.to] > d[u] + e.w) {
                d[e.to] = d[u] + e.w;
                p[e.to] = u;
                if (m[e.to] == 2) {
                    m[e.to] = 1;
                    q.push_back(e.to);
                } else if (m[e.to] == 0) {
                    m[e.to] = 1;
                    q.push_front(e.to);
                }
            }
        }
    }
}

这是我使用的网站的链接：D'Esopo-Pape
就特殊情况和时间复杂度而言，这并没有真正深入。

Answer 1

指数时间

这不是完整的证明，如果需要，您可以阅读“关于查找最短路径树的注释”（Aaron Kershenbaum，1981，https://doi.org/10.1002/net.3230110410）。您可能会感兴趣的另一个来源是“确定最短路径树的标记方法的属性”。

这个算法可能变坏的直观原因是，如果找到指向它的边，则再次从集合 M0 中拉出一个节点，以便稍后重新检查。这听起来已经是二次方了，因为可能有

|V|-1

边指向它，所以每个节点都可能“复活”很多次，但更糟糕的是：这种效果是自我放大的，因为每次节点“复活”时这样，从该节点发出的边可以导致更多的复活，依此类推。在完整的证明中，必须注意边权重，以确保足够多的“复活”能够“实际”发生，因为它们是有条件的，因此 [Kershenbaum 1981] 提出了一种构建实际示例的方法，在该示例上Pape 算法需要指数级的步骤。 顺便说一下，在同一篇论文中，作者说：

我使用该算法在非常大、非常稀疏的真实网络（数千个节点，平均节点度在 2 到 3 之间）中查找具有各种长度函数（通常与距离相关）的路由，并发现它优于所有其他算法.

（但由于没有人使用这个算法，所以没有太多可用的基准，除了

这个

，其中 Pape 的算法不比较如此有利） 相反，触发指数行为需要高度、邻接列表中特定边顺序以及不寻常的边权重的组合。提到了一些缓解措施，例如在运行算法之前按权重对邻接列表进行排序。

为什么很少使用

我找不到任何关于此的真正来源，并且不要指望它存在，毕竟你不必捍卫不使用一些具有奇怪属性的不寻常算法来启动。存在指数最坏情况（尽管经过仔细检查，它似乎不太可能被意外触发，而且无论如何 Simplex 算法都有指数最坏情况，并且它被大量使用），它相对未知，并且是唯一可用的实际的基准测试对算法“通常有效”的说法产生了怀疑（尽管我会注意到他们使用了 4 度，这似乎仍然很低，但它绝对高于声明中使用的“2 到 3 之间”该算法是有效的）。此外，即使没有触发指数行为，也不应该期望 Pape 的算法一般在稠密图上表现良好。