为什么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。它在特殊情况和时间复杂度方面并没有深入探讨。

- Marko

---

你真的在问为什么人们更喜欢最坏情况下是二次的算法（或者_V² log V_或其他）而不是通常很快但有时指数级的算法吗？ - Useless

是的，我已经编辑过了。问这样的问题有点愚蠢。因为我大部分时间都在进行竞赛编程（我还在读高中），所以我默认会做一些小任务（如果你愿意冒险，小优化可能会有所作为），而不是研究或真正的项目... - Marko

Answer 1

指数级时间复杂度

这里不会给出完整的证明，如果需要可以阅读 "A Note on Finding Shortest Path Trees" (Aaron Kershenbaum, 1981, https://doi.org/10.1002/net.3230110410)。另外一个有趣的参考资料是 "Properties of Labeling Methods for Determining Shortest Path Trees"。

该算法可能会失效的直观原因是，在找到指向集合M0内节点的边时，会将该节点从M0中取出以便后续再次检查。由于可能有|V|-1条边指向某个节点，因此每个节点都可能最多“复活”那么多次，这似乎已经是二次了，但实际上它更糟：这种影响具有自我放大性，因为每次以这种方式“复活”一个节点时，该节点的出度边会导致更多的复活，周而复始。在进行完整的证明时，需要对边权值进行一些仔细的处理，以确保有足够多的这些“复活”可以实际发生，因为它们是有条件的，因此[Kershenbaum 1981]提出一种方法来构建一个实际的例子，使Pape的算法需要指数级步骤。

顺便说一句，在同一篇论文中，作者表示：

我已经使用这个算法在非常大、非常稀疏的真实网络中（数千个节点和平均节点度数在2到3之间）找路线，并且使用了各种长度函数（通常与距离有关），并发现它的性能优于所有其他算法。

（但由于没有人使用此算法，因此没有太多可用的基准测试，除了这个，其中Pape的算法没有表现得那么出色）

与此相反，触发指数行为需要高度、邻接表中特定边的顺序以及异常边权值的组合。可以采取一些缓解措施，例如在运行该算法之前按权重对邻接列表进行排序。

为什么很少被使用

我没有找到任何真正的来源，也不指望有这样的来源存在，毕竟你不必为了不使用一些具有奇怪特性的不寻常算法而进行辩护。虽然有指数级别的最坏情况(但仔细检查后似乎不太可能意外触发，而且Simplex算法拥有指数级别的最坏情况，并且被广泛使用)，但它相对不知名，唯一可用的实际基准测试也对算法“通常有效”的说法产生了质疑(尽管我会注意到他们使用了4次方度数，这仍然似乎很低，但它肯定比声称该算法有效的“2到3之间”要高)。此外，即使没有触发指数级行为，也不应期望Pape算法在一般条件下对密集图表现良好。

- harold

---

非常感谢！第一次读到这个算法时，我真的很困惑，因为它在某些用例中似乎很有前途，但坏最坏情况的实际原因从未给出（仅提到）。 - Marko