为什么 D'Esopo-Pape 算法具有指数时间复杂度的最坏情况？
Why does D'Esopo-Pape algoritham have worst case of exponential time comlexity?
D'Escopo-Pape 算法在实现上与 Dijkstra 算法非常相似，并且适用于负权重边，但不适用于负循环。在大多数情况下，它显然比 Dijkstra 算法和 Bellman-Ford 算法更快。但是显然有这种算法需要指数时间的特殊情况，有人可以提供一些例子或者给我一些更彻底地分析这个算法的material。
这是实现：
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);
}
}
}
}
}
这是我使用的网站的 link：D'Esopo-Pape
就特殊情况和时间复杂度而言，这并没有真正深入。
指数时间
这不是完整的证明，如果需要，您可以阅读“寻找最短路径树的注意事项”（Aaron Kershenbaum，1981 年，https://doi.org/10.1002/net.3230110410）。您可能会感兴趣的另一个来源是“用于确定最短路径树的标记方法的属性”。
这个算法变坏的直观原因是集合 M0 中的一个节点被再次从中拉出，以便稍后在找到指向它的边时重新检查。这听起来已经是二次方了，因为可能有 |V|-1 条边指向它，所以每个节点都可能被“复活”多次，但更糟糕的是：这种效果是自我放大的，因为每次都有一个节点“复活” " 这样，从该节点传出的边可以导致更多的复活，等等。在完整的证明中，必须注意边缘权重，以确保足够多的“复活”可以 实际上 发生，因为它们是有条件的，所以 [Kershenbaum 1981] 提出了一个构建实际示例的方法，Pape 的算法需要指数级的步骤。
顺便说一句，作者在同一篇论文中说：
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.
（但由于没有人使用该算法，因此可用的基准测试不多，除了 this one，Pape 的算法没有比较好）
相比之下，触发指数行为需要结合高度、邻接列表中边的特定顺序以及不寻常的边权重。提到了一些缓解措施，例如在 运行 运行 算法之前按权重对邻接列表进行排序。
为什么很少使用
我找不到这方面的任何真正来源，也不指望它存在，毕竟你不必为不使用一些具有奇怪属性的不寻常算法而辩护。有一个指数最坏的情况（虽然仔细检查它似乎不太可能被意外触发，无论如何 Simplex 算法有一个指数最坏的情况，并且它使用了 lot），它是相对未知的，唯一可用的实际基准对算法“通常有效”的说法产生了怀疑（虽然我会注意到他们使用了 4 的度数，这看起来仍然很低，但它肯定高于“介于 2和 3" 用于声称该算法是有效的）。此外，即使未触发指数行为，也不应期望 Pape 算法在一般密集图上表现良好。
D'Escopo-Pape 算法在实现上与 Dijkstra 算法非常相似，并且适用于负权重边，但不适用于负循环。在大多数情况下，它显然比 Dijkstra 算法和 Bellman-Ford 算法更快。但是显然有这种算法需要指数时间的特殊情况，有人可以提供一些例子或者给我一些更彻底地分析这个算法的material。
这是实现：
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);
}
}
}
}
}
这是我使用的网站的 link：D'Esopo-Pape
就特殊情况和时间复杂度而言，这并没有真正深入。
指数时间
这不是完整的证明，如果需要，您可以阅读“寻找最短路径树的注意事项”（Aaron Kershenbaum，1981 年，https://doi.org/10.1002/net.3230110410）。您可能会感兴趣的另一个来源是“用于确定最短路径树的标记方法的属性”。
这个算法变坏的直观原因是集合 M0 中的一个节点被再次从中拉出，以便稍后在找到指向它的边时重新检查。这听起来已经是二次方了，因为可能有 |V|-1 条边指向它，所以每个节点都可能被“复活”多次，但更糟糕的是：这种效果是自我放大的，因为每次都有一个节点“复活” " 这样，从该节点传出的边可以导致更多的复活，等等。在完整的证明中，必须注意边缘权重，以确保足够多的“复活”可以 实际上 发生，因为它们是有条件的，所以 [Kershenbaum 1981] 提出了一个构建实际示例的方法，Pape 的算法需要指数级的步骤。
顺便说一句，作者在同一篇论文中说：
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.
（但由于没有人使用该算法，因此可用的基准测试不多，除了 this one，Pape 的算法没有比较好）
相比之下，触发指数行为需要结合高度、邻接列表中边的特定顺序以及不寻常的边权重。提到了一些缓解措施，例如在 运行 运行 算法之前按权重对邻接列表进行排序。
为什么很少使用
我找不到这方面的任何真正来源，也不指望它存在，毕竟你不必为不使用一些具有奇怪属性的不寻常算法而辩护。有一个指数最坏的情况（虽然仔细检查它似乎不太可能被意外触发，无论如何 Simplex 算法有一个指数最坏的情况，并且它使用了 lot），它是相对未知的，唯一可用的实际基准对算法“通常有效”的说法产生了怀疑（虽然我会注意到他们使用了 4 的度数，这看起来仍然很低，但它肯定高于“介于 2和 3" 用于声称该算法是有效的）。此外，即使未触发指数行为，也不应期望 Pape 算法在一般密集图上表现良好。