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

Question

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

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

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

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

Answer 1

Я не думаю, что это лучший способ, но вы можете создать узлы следующим образом:

Node:(NodeId, GraphId, correspondenceLeftCount) 

(общее число узлов будет number_of_initial_nodes * number_of_graphs * number_of_correspondences_allowed)

Итак:

Для края, где GraphId не изменяется, correspondenceLeftCount тоже не меняется. Вы добавляете новый край для переписки:

(NodeId, Graph1, correspondenceLeftCount) -> (NodeId, Graph2, correspondenceLeftCount - 1) `

И для запроса A-> B: Ваша точка старта являются (A, graph1, maxCorrespondenceLeftCount) и (A, graph2, maxCorrespondenceLeftCount).
И ваши конечные пункты (B, graph1, 0), ..., (B, graph1, maxCorrespondenceLeftCount), (B, graph2, 0), ..., (B, graph2, maxCorrespondenceLeftCount).

Таким образом, вам может потребоваться адаптировать реализацию Dijkstra для конечного состояния и уметь вставлять более одной начальной точки.