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

问题描述 投票:-1回答:1

我遇到了一个问题,我一直试图用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的算法 - 它很好但是边缘的每次修改都迫使我重新计算所有边缘。我几乎可以肯定存在更简单的方法。

c# algorithm graph-algorithm dijkstra
1个回答
1
投票

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

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

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

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

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

© www.soinside.com 2019 - 2024. All rights reserved.