Алгоритм поиска кратчайшего пути для занятых ребер

Question

Я хочу найти кратчайший путь на карте, аналогичный поездам в сети железных дорог. Под этим я подразумеваю, что есть ребра, которые заняты в определенное время, но которые свободны (например, поезд не может двигаться по краю в 6:38 вечера, так как в это время уже есть поезд на этой линии, нокрай свободен некоторое время спустя). Идея состоит в том, что всякий раз, когда выбирается маршрут, маршрут размещает «бронирование» для ребер, которые он посетит, так что никакой другой поезд не столкнется с любым другим.

Использование алгоритма Дейкстры недостаточно, так как алгоритмне может работать с узлами, чьи доступные соседи меняются: код может решить, что самый короткий маршрут от B до C составляет 6 единиц расстояния, но когда алгоритм находит более короткий маршрут от A до B, это означает, что поезд прибывает через пару минутранее, что, в свою очередь, может привести к недоступности края BC.

Для простоты я предполагаю, что поезда не могут остановиться, чтобы дождаться открытия линии, и я предполагаю, что «поезда»ведут себя как автомобили в том смысле, что они исчезают после использования, и нет никакой возможности, ни необходимости менять поезда (все поезда могут пересекать все края).

Как я могу реализовать алгоритм (вероятно, основанный на Дейкстре), который выполняетэто?

Помощь приветствуется.

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

Вы пишете: «Предположим, что поезда не могут остановиться, чтобы дождаться открытия линии». Однако, если вы позволите поезду «ждать», чтобы открыть линию, выбирая более длинный маршрут докрай, где линия закрыта, и это возможно и все же быстрее, чем любой другой маршрут, тогда вышеупомянутый алгоритм пропустит это.