我在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))
会容易得多。
你能帮我解决吗?我不明白问题中给出的提示。
最佳答案
我同意,这是一个令人困惑的问题。这是我对此的一些想法。
通过将原始成本替换为降低的成本,将A* search算法简化为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 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/