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