Кратчайший путь в «двухграфе» с ограниченным количеством изменений

Допустим, у нас есть два ориентированных и положительно взвешенных графика на одном наборе вершин (первый график представляет, например, железные дороги, а второй - автобусные полосы; вершины - это автобусные остановки или железнодорожные станции или оба). Нам нужно найти кратчайший путь от A до B, но мы не можем изменить тип транспорта более чем в N раз.

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

Как наилучшим образом представить этот «двухграф» и как управлять ограниченным количеством изменений в обходе графа? Есть ли возможность адаптировать алгоритм Дейкстры в этом? Любые идеи и подсказки будут полезны.

Редактировать: Ну, я забыл одну вещь (я думаю, что это очень важно): N = 0,1,2, ...; мы можем придумать любое графическое представление, которое нам нравится, и, конечно, может существовать максимум 4 ребра между каждыми двумя узлами (1 полоса движения и 1 железная дорога в одном направлении, и 1 полоса движения автобусов и 1 железная дорога во втором направлении).

Ответы на вопрос(1)

Ваш ответ на вопрос