最短路径上最重要的边缘

Question

我有这个问题上形成算法的塞奇威克的课程:" 批判锋芒给定一个边加权有向图,设计一个.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))需要先进的数据结构,我认为它是在图形上(不是有向图).如果它有三位先进的计算机科学家来开发这种算法,对于入门课程来说难道不是太大的问题吗？但也许它更容易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 到 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)的最大增加。实际上，如果w和t之间的边之一缺失，则可以通过顶点u从w到t。另一方面，请注意移除最后一条边(v, t)将导致这种增加。

现在，只需用w迭代t所做的事情。找到一个顶点x使得c'(x, w)是最小值并且x不在最短路径上。沿着从s到x的最短路径向后走，直到到达属于从s到w的最短路径的顶点。

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

Answer 2

这是一个令人困惑的问题，我同意。以下是我对此的一些想法。

\n\n

减少A* 搜索时使用“减少成本”术语和定义当通过用减少的成本替换原始成本来

\n\n

c\xe2\x80\xb2(v,w) = c(v,w) - h(v) + h(w) = c(v,w) - (h(v) - h(w)) > 0

\n\n

该h(v) - h(w)部分是启发式函数的下降，在一致（单调）启发式的情况下，该函数不应超过边缘成本，因此降低的成本仍然大于 0（请参见此处的幻灯片 14 和 15 ））

\n\n

看起来 Sedgewick 建议d(v)在搜索新的/替换的最短路径时使用原始距离函数 ( ) 作为一致的启发式，其中G\'与原始的最短路径相同G，但沿着从s到 的原始最短路径删除了一条边t。就我个人而言，我不认为它如何有助于解决最重要的边缘问题O(ElogV)。

\n\n

还有一个类似的问题：找到图中所有向下和向上的临界边。根据定义，降低向下临界边的成本会降低总体 SP 成本。增加向上临界边的成本会增加总体 SP 成本。所有关键边都可以在此处找到O(ElogV)，请参阅第 8 章。但这并没有回答什么边缘是最关键的问题（导致删除时最大 SP 增加）。

\n\n

正如您所指出的，最重要的边缘问题已被 Malik、Mittal 和 Gupta (1989) 及时解决O(E + V*log(V))。我还没有找到原始的 MMG 论文，但是这个演示文稿很好地解释了它。据我所知，可以通过优先级队列来解决，不需要特定的数据结构。

\n\n

很抱歉没有真正回答最初的问题（使用降低的成本解决有向图中最重要的边缘的问题），但仍然希望上面的链接和想法可能对某人有用。我很高兴看到塞奇威克提出的解决方案。

\n