我在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)) > 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/