Кратчайший путь в «двухграфе» с ограниченным количеством изменений
Допустим, у нас есть два ориентированных и положительно взвешенных графика на одном наборе вершин (первый график представляет, например, железные дороги, а второй — автобусные полосы; вершины — это автобусные остановки или железнодорожные станции или оба). Нам нужно найти кратчайший путь от A до B, но мы не можем изменить тип транспорта более чем в N раз.
Я пытался модифицировать алгоритм Дейкстры, но он работает только на нескольких «не очень подлых и сложных» графиках, и я думаю, что мне нужно попробовать что-то другое.
Как наилучшим образом представить этот «двухграф» и как управлять ограниченным количеством изменений в обходе графа? Есть ли возможность адаптировать алгоритм Дейкстры в этом? Любые идеи и подсказки будут полезны.
Редактировать: Ну, я забыл одну вещь (я думаю, что это очень важно): N = 0,1,2, …; мы можем придумать любое графическое представление, которое нам нравится, и, конечно, может существовать максимум 4 ребра между каждыми двумя узлами (1 полоса движения и 1 железная дорога в одном направлении, 1 полоса движения и 1 железная дорога во втором направлении).
Решение
Я не думаю, что это лучший способ, но вы можете создавать узлы следующим образом:
Node:(NodeId, GraphId, correspondenceLeftCount)
(общее количество узлов будет number_of_initial_nodes * number_of_graphs * number_of_correspondences_allowed)
Так:
Для края где GraphId не меняется, correspondenceLeftCount не меняется ни
Вы добавляете новый Edge для соответствия:
(NodeId, Graph1, correspondenceLeftCount) -> (NodeId, Graph2, корреспонденцииLeftCount — 1) `
А для запроса А-> Б:
Ваша отправная точка (A, graph1, maxCorrespondenceLeftCount) а также (A, graph2, maxCorrespondenceLeftCount),
И ваши конечные точки (B, graph1, 0), …, (B, graph1, maxCorrespondenceLeftCount), (B, graph2, 0), …, (B, graph2, maxCorrespondenceLeftCount),
Так что вам, возможно, придется адаптировать вашу реализацию Dijkstra для конечное условие, и чтобы иметь возможность вставить более одной начальной точки.
Другие решения
Других решений пока нет …