1

Задача: найти и вывести первый и второй (который может совпадать с первым) наименьший путь в графе. И если с первым пунктом всё понятно (алгоритм Дейкстры), то как нужно поступить с вторым путем (используя этот же алгоритм Дейкстры)? Поиск ответвлений с большим или равным значением,чем в 1 пути не всегда верен т.к. второй наименьший путь может идти совсем другой дорогой. Может быть есть какой-то лучший алгоритм?

2
  • Постарайтесь писать более развернутые вопросы. Поясните, в чем именно вы видите проблему, как её воспроизвести, что вы хотите получить в результате, приведите пример вашей текущей реализации и т. д. 25 мая 2016 в 3:32
  • В основном это был теоретический вопрос(что видно из тегов).Но если нужно конкретнее то без проблем.Сам код взял с geeksforgeeks.org/… (с\с++).Проблема в том, что алгоритм находит только 1 значение соответствующее минимальному значению из одного узла в другой(функция mindistance).При этом поиск второго минимального значения в этой функции (через if) не помогает т.к. второй наименьший путь может проходить через другие узлы. 25 мая 2016 в 6:29

2 ответа 2

2

Да есть, существует несколько способов решения. Самый простой - находим кратчайший путь и перебираем в цикле ребро, которого не будет во 2 пути. Из всех таких оставить оптимальный, псевдокод:

val second_path = inf;
val opt_path =  Dejkstra();
for (edge : opt_path){
    edge.del();
    second_path = min(second_path, Dejkstra() );  
    edge.add();
}

Сложность что-то порядка O( N*(N*logN + M) ); Если надо быстрее, то есть способ. Рассмотрим оставное дерево, образованное всеми оптимальными путями от 1 вершины до остальных. (Почем дерево думаю очевидно). После чего мы должны на путь из 1 в K к примеру, использовать РОВНО 1 ребро не из дерева. Дальше - динамика по дереву. Опишу идею: либо мы поднимаемся выше по этой ветке дерева, либо мы перепрыгиваем на соседнее, в любом случае у нас есть оптимальное значение пути которое мы момжем использовать.

Сложность: сложность Дейкстры = O(N log N + M).

Кстати оба алгоритма ищут все 2 пути из выбранной вершины.

1

Решено, подсказали решение алгоритмом - https://en.wikipedia.org/wiki/Yen%27s_algorithm либо второе решение(используя алгоритм Дейкстры) - найти минимальный путь до всех соседей целевого узла, выбрать из них самый минимальный , проверить совпадает ли он с 1 минимальным.Если совпадает - найти следущий минимальный.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.