c++algorithmtime-complexity

Why does the D'Esopo-Pape algorithm have a worst case exponential time complexity?


D'Escopo-Pape algorithm is very similar in implementation to the Dijkstra's algorithm and works with negative weight edges but it doesn't work with negative cycles. It is apparently faster then Dijkstra's algorithm and Bellman-Ford algorithm in most cases. But there are apparently special cases where this algorithm takes exponential time.

Can someone provide some example or point me to some material that analyses this algorithm more thoroughly?

This is the implementation:

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);
                }
            }
        }
    }
}

This is the link of the site I used: D'Esopo-Pape
Which doesn't really go in depth in terms of special cases and time-complexity.


Solution

  • Exponential time

    This won't be a full proof, you can read "A Note on Finding Shortest Path Trees" (Aaron Kershenbaum, 1981, https://doi.org/10.1002/net.3230110410) if you want that. An other source you may find interesting is "Properties of Labeling Methods for Determining Shortest Path Trees".

    The intuitive reason why this algorithm can go bad is that a node in set M0 is pulled out from it again to be re-examined later if an edge that points to it is found. That already sounds quadratic because there could be |V|-1 edges pointing to it, so every node could potentially be "resurrected" that many times, but it's even worse: that effect is self-amplifying because every time a node is "resurrected" in that way, the edges outgoing from that node can cause more resurrections, and so on. In a full proof, some care must be taken with the edge weights, to ensure that enough of those "resurrections" can actually happen, because they are conditional, so [Kershenbaum 1981] presents a way to build an actual example on which Pape's algorithm requires an exponential number of steps.

    By the way, in the same paper the author says:

    I have used this algorithm to find routes in very large, very sparse real networks (thousands of nodes and average nodal degree between 2 and 3) with a variety of length functions (generally distance-related) and have found it to outperform all others.

    (but since no one uses this algorithm, there are not many available benchmarks, except this one in which Pape's algorithm does not compare so favourably)

    In contrast, triggering the exponential behaviour requires a combination of a high degree, a particular order of edges in the adjacency list, and unusual edge weights. Some mitigations are mentioned, for example sorting the adjacency lists by weight before running the running the algorithm.

    Why is it rarely used

    I could not find any real source on this, and don't expect it to exist, after all you would not have to defend not-using some unusual algorithm that has strange properties to boot. There is the exponential worst case (though on closer inspection it seems unlikely to be triggered by accident, and anyway the Simplex algorithm has an exponential worse case, and it is used a lot), it is relatively unknown, and the only available actual benchmark casts doubt on the claim that the algorithm is "usually efficient" (though I will note they used a degree of 4, which still seems low, but it is definitely higher than the "between 2 and 3" used in the claim that the algorithm is efficient). Also, it should not be expected that Pape's algorithm will perform well on dense graphs in general, even if the exponential behaviour is not triggered.