令 G = (V, E) 为边权重非负的连通有向图，令 s 和 t 为 G 的顶点，令 H 为 G 删除部分边得到的子图。假设我们想将 G 的一条边重新插入到 H 中，以便在结果图中从 s 到 t 的最短路径尽可能短。描述和分析一种算法，以选择要重新插入的最佳边。
我认为它需要与我们删除的每条边一起使用贝尔曼福特算法，然后从所有路径中找到最短路径..但是这个运行时间太大了..有人有其他想法吗？谢谢 ：）
问问题
2100 次
1 回答
1
令 e[1] = (u[1],v[1]), e[2] = (u[2],v[2]), ..., e[N] = (u[N], v[N]) 是从 G 中移除的边以得到 H。
从 s 开始在 H 上运行 Dijkstra 算法，跟踪到 {u[1], u[2], ..., u[N]} 的最短路径的成本，我们将其称为 A(n)对于每个节点 n。
在 H 上运行 Dijkstra 算法，所有边从 t 开始反转，跟踪到 {v[1], v[2], ..., v[N]} 的最短路径的成本，我们将其称为每个节点 n 的 B(n)。
那么重新插入 H 的最佳单边是边 i 使得 A(u[i]) + c(e[i]) + B(v[i]) 最小化。
该算法运行 Dijkstra 算法两次，因此该部分的复杂度为 O(|E| + |V|log|V|) 其中 |E| 是边数，|V| 是节点数。
（我故意忽略了从 s 到 t 的最短路径不涉及任何已删除的边缘或从 s 到 t 不存在的路径的琐碎情况。它们不会对一般方法造成任何问题，但你需要在实现中注意它们。）
于 2016-01-12T18:39:14.463 回答