Shortest path finding algorithm for occupied edges

Question

I want to find the shortest path in a map similar to trains on a rail network. With that, I mean that there are edges which are occupied at a certain time but which are free (e.g., a train can't run an edge at 6:38 pm as there is already a train on that line at that time, but the edge is free a while later). The idea is that whenever a route is decided upon, the route places a 'booking' for the edges it will visit so that no other train will collide with any other.

Using Dijkstra's algorithm is not sufficient as the algorithm can't deal with nodes whose available neighbours change: the code might decide the shortest route from B to C is 6 units of distance, but when the algorithm finds a shorter route from A to B, which means the train arrives a couple of minutes earlier, which in turn can lead to the edge B-C not being available.

For simplicity's sake, I assume that the trains can't stop to wait for a line to open up and I assume that the 'trains' behave like cars in the sense that they disappear after usage and there is no option nor need to change trains (all trains can traverse all edges).

How could I implement an algorithm (likely Dijkstra-based) which accomplishes this?

Help is appreciated.

ravenspoint ravenspoint · Accepted Answer · 2019-10-31T21:08:58

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

You write: "assume that the trains can't stop to wait for a line to open up" However if you allow a train to "wait" for a line to open up by taking a longer route to the edge where the line is closed and this is feasible and still faster than any other route, then the above algorithm will miss this.

Shortest path finding algorithm for occupied edges

1 Answers