evlevin
@evlevin

Как найти 3 кратчайших пути в графе?

Найти 3 самых коротких пути в графе. То есть вывести топ-3 коротких путей.
Как исключить первый путь при поиске второго? И первые два при поиске третьего?
  • Вопрос задан
  • 731 просмотр
Решения вопроса 1
bobrovskyserg
@bobrovskyserg
Трудно тебе будет.
1. Находишь путь.
2. Из этого пути поочередно удаляешь по ребру и строишь путь в графе без ребра. Один из вариантов (или несколько) будут кратчайшими. Если несколько - задача решена.
3. Если нет - ну ты понел...
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
LittleFatNinja
@LittleFatNinja
горе девелопер, любитель лютой садомии
Mrrl
@Mrrl
Заводчик кардиганов
В каждой вершине хранить не более трёх кратчайших путей до неё. В Дейкстре использовать очередь без модификации веса. Если очередной путь, взятый из очереди, лучше третьего по порядку пути, сохранённого в вершине, (или сохранено не более двух путей) - добавляем этот путь в вершину, а все его продолжения - в очередь.
Проблема в том, что в путях могут появиться циклы. Например, для графа из двух вершин с тремя рёбрами
(1,2, w=1)
(1,2, w=3)
(1,2, w=5)
будут выданы пути 1-2 (по первому ребру), 1-2 (по второму ребру) и 1-2-1-2 (по первому ребру). Если циклы нежелательны - придётся возиться дольше
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы