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

Question

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

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

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

我如何实现实现此目的的算法（可能基于 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

你写："assume that the trains can't stop to wait for a line to open up" 但是，如果你允许火车 "wait" 通过走更长的路线到线路关闭的边缘来打开线路，这是可行的，而且仍然比任何其他路线都快，那么上述算法将错过这一点。

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

Shortest path finding algorithm for occupied edges

algorithm

graph

dijkstra

shortest-path