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
就特殊情况和时间复杂度而言,这并没有真正深入。
这不是完整的证明,如果需要,您可以阅读“关于查找最短路径树的注释”(Aaron Kershenbaum,1981,https://doi.org/10.1002/net.3230110410)。您可能会感兴趣的另一个来源是“确定最短路径树的标记方法的属性”。
这个算法可能变坏的直观原因是,如果找到指向它的边,则再次从集合 M0 中拉出一个节点,以便稍后重新检查。这听起来已经是二次方了,因为可能有
|V|-1
边指向它,所以每个节点都可能“复活”很多次,但更糟糕的是:这种效果是自我放大的,因为每次节点“复活”时这样,从该节点发出的边可以导致更多的复活,依此类推。在完整的证明中,必须注意边权重,以确保足够多的“复活”能够“实际”发生,因为它们是有条件的,因此 [Kershenbaum 1981] 提出了一种构建实际示例的方法,在该示例上Pape 算法需要指数级的步骤。
顺便说一下,在同一篇论文中,作者说:
我使用该算法在非常大、非常稀疏的真实网络(数千个节点,平均节点度在 2 到 3 之间)中查找具有各种长度函数(通常与距离相关)的路由,并发现它优于所有其他算法.
这个(但由于没有人使用这个算法,所以没有太多可用的基准,除了
,其中 Pape 的算法不比较如此有利) 相反,触发指数行为需要高度、邻接列表中特定边顺序以及不寻常的边权重的组合。提到了一些缓解措施,例如在运行算法之前按权重对邻接列表进行排序。
为什么很少使用