删除后选择最佳边重新插入的算法
an algorithm to choose the best edge to reinsert after deleting
设G = (V, E)为边权非负的连通有向图，s、t为G的顶点，H为G删除部分边得到的子图。假设我们想要从 G 中恰好将一条边重新插入到 H 中，以便生成的图中从 s 到 t 的最短路径尽可能短。描述并分析一种算法，以选择要重新插入的最佳边缘。
我认为它需要与我们删除的每条边一起使用 bellman-ford 算法，
然后找到所有的最短路径..
但是 运行 这个时间太大了.. 任何人有其他想法吗？
谢谢:)
设 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]} 的最短路径的成本，我们将为每个节点 n.
调用 A(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 的路径的琐碎情况。它们不会对一般方法造成任何问题，但是您需要在实施中注意它们。）
设G = (V, E)为边权非负的连通有向图，s、t为G的顶点，H为G删除部分边得到的子图。假设我们想要从 G 中恰好将一条边重新插入到 H 中，以便生成的图中从 s 到 t 的最短路径尽可能短。描述并分析一种算法，以选择要重新插入的最佳边缘。
我认为它需要与我们删除的每条边一起使用 bellman-ford 算法， 然后找到所有的最短路径.. 但是 运行 这个时间太大了.. 任何人有其他想法吗？ 谢谢:)
设 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]} 的最短路径的成本，我们将为每个节点 n.
调用 A(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 的路径的琐碎情况。它们不会对一般方法造成任何问题，但是您需要在实施中注意它们。）