#algorithm #graph-theory #shortest-path #dijkstra
#алгоритм #теория графов #кратчайший путь #dijkstra
Вопрос:
Я думаю, что для каждого ребра в наборе ребер, из которых я могу выбрать, создайте копию графика с вставленным в него этим ребром, а затем запустите Дейкстру. Лучшее ребро будет из графика с наименьшим общим весом в конце.
Но это кажется неэффективным. Мне пришлось бы вызывать Дейкстру для каждого ребра в наборе. Есть ли лучший способ сделать это?
Комментарии:
1. Вы минимизируете все кратчайшие пути или один конкретный путь, пожалуйста?
2. @Shamis О, извините, я забыл упомянуть. Существует существующий путь между начальной точкой и конечной точкой, и я пытаюсь минимизировать только этот путь. Итак, только 1 конкретный путь.
Ответ №1:
Грязный трюк:
Запустите Djikstra над измененным графиком. Этот граф будет включать все вершины и ребра из исходного графа. Дважды.
Для каждой вершины i создайте вершину i’. Если было ребро (u, v), создайте ребро (u ‘, v’). В результате у нас есть два графика, которые выглядят одинаково, кроме «s».
Теперь начинается волшебный трюк:
- Для каждого ярлыка x, y создайте ребро (x, y’).
- Объединить цель и цель ‘
Запуск Djikstra над этим графиком даст вам кратчайший путь, включая ярлыки. Почему?
- Если ярлыки по каким-то причинам не помогают, мы находимся в исходном графике, и результат не меняется.
- Если мы решим использовать сокращение, мы застрянем в скопированном графике и не сможем вернуться назад — следовательно, мы можем использовать только одно сокращение. Поскольку цель является единственным «сингулярным» узлом с момента его объединения, мы все равно можем его достичь.
Следовательно, если Djikstra найдет путь в этом модифицированном графе, у нас будет наш новый кратчайший путь, который учитывает ярлыки.
Результирующая сложность задается Djikstra, и поскольку мы добавили в микс только ребра E len (ярлыки), ничего не изменилось по сравнению с исходной Djikstra.
Комментарии:
1. Я просто набирал то же самое, но вы меня опередили. 1
2. Это действительно умное решение! Столкнется ли это с проблемой поиска только первого ребра, которое уменьшает путь, а не наиболее оптимального ребра? @BlueRaja-Даннипфлюгоефт и Шамис
3. @Mike729: Дейкстра находит кратчайший путь, чтобы найти оптимальное ребро, если таковое имеется.
4. «Мы застряли во 2-м графике» — это просто способ представить, почему кратчайший путь, который мы находим, правильный. Djikstra — это алгоритм типа «распространения волны», поэтому застревает только одна часть волны, остальная часть продолжается в исходном графике / застревает в разных местах. Часть волны, которая первой доходит до целевого узла, — это та, которая проходит по кратчайшему пути.