我在 Sedgewick 的算法课程中有这个问题：“临界边。给定一个边加权有向图，设计一个算法来找到一条边，该边的去除会导致从到E*log(V)的最短路径的长度最大增加（可能是无限的）。假设所有边缘权重都严格为正。（提示：计算到的最短路径距离并考虑降低的成本。）“std(v)svc′(v,w)=c(v,w)+d(v)−d(w) ≥ 0
我在互联网上读到，三 (3) 人在 1989 年提出了一种复杂的算法，O(E + V*log(V))需要高级数据结构，我认为它是在图表上（而不是有向图）。如果它有三位高级计算机科学家来开发这种算法，对于入门课程来说不是太大的问题吗？但也许它更容易O(E*log(V))。
你能帮我解决吗？我不明白问题中给出的提示。
这是根据 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到t的最短路径是(s, ..., v, t)并且我们删除最后一条边(v, t)。然后，从s到t的最短路径长度的增加等于所有入边(u, t)的c'(u, t)的最小值，其中u != v。
假设u使得c'(u, t)是最小值（仍然是u != v）。然后沿着从s到u的最短路径向后，直到到达一个顶点，比如说w，属于从s到t的最短路径（没有任何删除的边）。从s到t的最短路径类似于(s, ..., w, ..., v, t)。
请注意，如果您删除w和t之间的任何边，您将获得c'(u, t) int 最短路径的最大增加。实际上，如果w和t之间的一条边丢失，则通过顶点u从w到t就足够了。另一方面，请注意，删除最后一条边(v, t)将导致这种增加。
现在，只需用w迭代t所做的事情。找到一个顶点x使得c'(x, w)是最小值并且x不在最短路径上。沿着从s到x的最短路径向后移动，直到到达属于从s到w的最短路径的顶点。
到达s后，您就可以确定要删除哪个顶点以最大程度地增加最短路径的长度。
这是一个令人困惑的问题，我同意。以下是我对此的一些想法。
“降低成本”一词和定义用于将A* 搜索算法简化为 Dijkstra 算法，将原始成本替换为降低的成本：
c′(v,w) = c(v,w) - h(v) + h(w) = c(v,w) - (h(v) - h(w)) > 0
该h(v) - h(w)部分是启发式函数的下降，在一致（单调）启发式的情况下不应超过边缘成本，因此降低的成本仍然大于 0（参见此处的幻灯片 14 和 15 ）
看起来 Sedgewick 建议d(v)在搜索新的/替换最短路径时使用G'原始距离函数( 就个人而言，我看不出它如何帮助解决最重要的边缘问题。GstO(ElogV)
还有一个类似的问题：找出图中所有向下和向上的临界边。根据定义，降低向下临界边缘的成本会降低整体 SP 成本。增加向上临界边缘的成本会增加整体 SP 成本。所有关键边缘都可以在 中找到O(ElogV)，请参阅此处的第 8 章。但这并不能回答什么边缘是最关键的问题（移除时导致最大 SP 增加）。
正如您所指出的，Malik、Mittal 和 Gupta (1989)
O(E + V*log(V))及时解决了最重要的边缘问题。我还没有找到原始的 MMG 论文，但是这个演示文稿很好地解释了它。据我所知，它可以通过优先级队列来解决，不需要特定的数据结构。
很抱歉没有真正回答原始问题（使用降低成本的有向图中最重要的边缘的解决方案），但仍然希望上面的链接和想法可能对某人有用。我很高兴看到 Sedgewick 的解决方案。