algorithm - 占用边的最短路径查找算法

Question

我想在 map 中找到最短路径，类似于铁路网上的火车。这样，我的意思是有些边缘在某个时间被占用但空闲(例如，火车不能在下午 6:38 运行边缘，因为当时该线路上已经有火车，但是一段时间后边缘是空闲的)。这个想法是，无论何时决定一条路线，该路线都会为其将要访问的边缘放置一个“预订”，这样其他火车就不会与任何其他火车相撞。

使用 Dijkstra 算法是不够的，因为该算法无法处理可用邻居发生变化的节点:代码可能决定从 B 到 C 的最短路线是 6 个距离单位，但是当算法找到从 A 到更短的路由时到 B，这意味着火车提前几分钟到达，这反过来可能导致边 B-C 不可用。

为简单起见，我假设火车不能停下来等待线路开通，并且我假设“火车”的行为就像汽车，因为它们会在使用后消失，没有选择也不需要换车(所有火车都可以穿过所有边)。

我如何实现实现此目的的算法(可能是基于 Dijkstra 的算法)？

感谢您的帮助。

Answer 1

solution loop
    run dijkstra
    set conflict flag false
    loop over edges in shortest path
       calculate time at edge
       if conflict
            set conflict flag true
            remove edge
            break from loop over edges
    loop over edges end
    if conflict flag false
        solved!
solution loop end

您写道:“假设火车不能停下来等待线路开通”但是，如果您允许火车“等待”线路开通，方法是采取更长的路线到达线路所在的边缘线路关闭并且这是可行的并且仍然比任何其他路线更快，那么上述算法将错过这一点。