我在Sedgewick的算法类(class)中提出了这个问题:“临界边。给定一个边加权的有向图,设计一个E*log(V)算法来查找一条边,该边的去除会导致从到的最短路径长度的最大增加(可能是无限的)。 st。假定所有边缘权重都严格为正。(提示:计算从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))会容易得多。

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

最佳答案

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

通过将原始成本替换为降低的成本,将A* search算法简化为Dijkstra的算法时,将使用“降低的成本”术语和定义:
c′(v,w) = c(v,w) - h(v) + h(w) = c(v,w) - (h(v) - h(w)) > 0h(v) - h(w)部分是启发式函数的一部分,在一致(单调)启发式的情况下,它不应超过边缘成本,因此降低的成本仍大于0(请参见幻灯片14和15 here)

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

还有一个类似的问题:在图中找到所有向下和向上的临界边。根据定义,降低下临界边缘的成本会降低整体SP成本。向上临界边缘的成本增加会增加整体SP成本。所有关键边缘都可以在O(ElogV)中找到,请参阅第8章here。但这并不能回答哪个边缘最关键的问题(导致移除后最大SP增大)。

如您所述,最重要的边缘问题由Malik,Mittal和Gupta(1989)解决。O(E + V*log(V))时间。我没有找到原始的MMG纸,但是this presentation很好地解释了它。据我所知,可以使用优先级队列来解决它,而无需特定的数据结构。

对不起,您实际上没有回答原始问题(使用降低的成本解决了有价证券中最重要的问题的解决方案),但仍然希望上面的链接和思想可能对某人有用。我很高兴看到Sedgewick提出的解决方案。

关于graph - 最短路径上最重要的优势,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/16291489/

10-12 18:06
查看更多