查找图表中可能发生变化的最短路径[关闭]

Question

我遇到了一个问题，我一直试图用dijkstra的算法来解决这个问题。任务：我们有N个城市，M“边缘”。每个连接都有一个构建日期和时间。一些路线正在修改，但时间只在减少。

例：

1780,1,3,50，b //在1780年，从1到3在50小时内，b - 建造，m - 修改

1784,1,2,30，b

1784,2,3,10，b

1810,1,3,38，m

我正在寻找可能在不到40小时内连接1到3之间的日期。所以在1810年修改之前连接<40小时不存在。结果是1810年。

关键是要知道是否有可能在不到X小时内从A市进入B市。所以我实现了dijkstra的算法 - 它很好但是边缘的每次修改都迫使我重新计算所有边缘。我几乎可以肯定存在更简单的方法。

Answer 1

Dijkstra的算法可以使用Min-Heap实现，在这种情况下，它应该使用它来实现，因为它具有可以处理以下内容的减少键操作：

一些路线正在修改，但时间只在减少。

一旦你理解了最小堆，你就会知道你不需要重新计算所有的边，一个简单的减少键操作在时间O（logn）就足够了。

一旦你理解了Min-Heap数据结构，请转到这个link以了解如何使用Min-Heaps实现Dijkstra，之后你需要做的唯一额外事情是每当成本降低时应用另一个reduce-key操作。

我建议在进行实施之前仔细阅读这些链接。