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