graph - 最短路径上最重要的边缘

Question

我在 Sedgewick 的算法类(class)中有这个问题:“ 临界边 。给定一个边加权有向图，设计一个 E*log(V) 算法来找到一条边，其去除导致最大增加(可能是无限)从 s 到 t 的最短路径的长度。假设所有边权重都严格为正。(提示:计算最短路径距离 d(v) 形式 s 到 v 并考虑降低的成本 c′(v,w)=c(v,w)+d(v)−d(w) ≥ 0 | .)”

我在互联网上读到，1989 年三 (3) 个人想出了一个复杂的算法 O(E + V*log(V))什么需要高级数据结构，我认为它是在图上(不是有向图)。如果让三位高级计算机科学家来开发这个算法，对于入门类(class)来说是不是太麻烦了？但也许只是 O(E*log(V)) 更容易.

你能帮我解决吗？我不明白问题中给出的提示。

Answer 1

这是找到 的算法的草图临界边缘在最短路径上，基于 Sedgewick 的提示。

一、降低成本 c′(v,w)=c(v,w)+d(v)−d(w) 对应于从 开始的最短路径长度的增加s 至 w ，当通过 v 之前 w . (如果 v 在从 s 到 w 的最短路径中，那么这个增加是 0。)(实际上是最短路径的长度 d(v)从 s 到 v 和 c(v, w) 是从 v 到 w 的成本。)

假设来自 的最短路径s 至 电话 是 (s, ..., v, t) 我们删除最后一条边 (v, t) .然后从增加最短路径的长度s 至 电话 等于 的最小值c'(u, t) 适用于所有边缘 (u, t) , 与 你 != v .

假设 u 是这样的 c'(u, t) 是最小值(仍然是 u != v )。然后按照最短路径 s 至 u 向后，直到到达顶点，例如 w ，属于距离的最短路径s 至 电话 (没有任何去除的边缘)。来自 的最短路径s 至 电话 类似于 (s, ..., w, ..., v, t)。



请注意，如果删除 之间的任何边缘w 和 电话 ，您将获得最大增加 c'(u, t) int 最短路径。事实上，万一之间的边之一w 和 电话 不见了，从就够了w 至 电话 通过顶点 u .另一方面，请注意删除最后一条边 (v, t) 将导致这种增加。

现在，只需迭代 w 用 做了什么|电话 .找一个顶点 x 使得 c'(x, w) 是最小值和 x 不在最短路径上。遵循来自 的最短路径s 至 x 向后直到到达属于最短路径的顶点 s 至 w .

一旦您到达 s 然后您就可以确定要移除哪个顶点以最大程度地增加最短路径的长度。