为何D'Esopo-Pape算法最坏时间复杂度为指数级？有无相关分析资料及示例？

D'Esopo-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);
                }
            }
        }
    }
}

指数级复杂度特殊场景示例 #

可以通过构造特定的负权链式图触发最坏情况：

• 总共有n个节点，编号为0~n-1，起点设为0
• 对所有1 ≤ i ≤ n-1，添加边i → i-1，边权为-1
• 对所有0 ≤ i ≤ n-2，添加边0 → i，边权为2^i

该场景下节点的总入队次数为2^(n-1)，时间复杂度退化为指数级。核心原因是算法规则中，已出队的节点如果被松弛会优先插入队头处理，该规则在上述构造图中会导致每次节点松弛都触发大量重复的后续松弛操作，双端队列的优化逻辑完全失效。

算法特性补充说明 #

• 无负权边场景下，算法时间复杂度稳定为O(m)（m为边数），效率高于堆优化Dijkstra算法
• 含负权边的随机稀疏图场景下，算法平均时间复杂度接近线性，远优于Bellman-Ford的O(nm)
• 仅在人为构造的极端负权图场景下才会出现指数级退化，工业界大部分实际使用场景不会触发该问题

内容的提问来源于stack exchange，提问作者Marko