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

Question

[Евгений]

Найти 3 самых коротких пути в графе. То есть вывести топ-3 коротких путей.
Как исключить первый путь при поиске второго? И первые два при поиске третьего?

Answer 1

[bobrovskyserg]

Трудно тебе будет.
1. Находишь путь.
2. Из этого пути поочередно удаляешь по ребру и строишь путь в графе без ребра. Один из вариантов (или несколько) будут кратчайшими. Если несколько - задача решена.
3. Если нет - ну ты понел...

Answer 2

[LittleFatNinja]

дейкстра

Comments

[Евгений]

Но как исключить первый путь при поиске второго? И первые два при поиске третьего?

[Praytic]

Логично, наверное, что после того, как мы нашли первый путь он будет топ 1 кратчайшим, а следующий, который найдем топ 2 и так далее.

[Евгений]

Praytic: это ясно. Но как сделать, чтобы при поиске второго снова не найти первый путь? То есть исключить первый путь.

[bobrovskyserg]

Praytic:
Очень остроумно - прибить вершину, в которую нужно проложить путь.

[Praytic]

Еще способ просто восстановить все пути из массива предков, занести их в вектор векторов, отсортить его и вывести просто первые три пути. Самый простой способ.

[Евгений]

Praytic: что вы имеете в виду под вектором векторов?

[Praytic]

Евгений: Двумерный вектор, которй будет содержать все кратчайшие пути во все вершины.
www.cs.usfca.edu/~galles/visualization/Dijkstra.html
Вот тут хорошая визуализация алгоритма и в конце показано восстановление путей. Поэтому всевозможные пути записываем в этот двумерный вектор, сортируем по возрастанию и первые три пути будут кратчайшими.

Answer 3

[Mrrl]

В каждой вершине хранить не более трёх кратчайших путей до неё. В Дейкстре использовать очередь без модификации веса. Если очередной путь, взятый из очереди, лучше третьего по порядку пути, сохранённого в вершине, (или сохранено не более двух путей) - добавляем этот путь в вершину, а все его продолжения - в очередь.
Проблема в том, что в путях могут появиться циклы. Например, для графа из двух вершин с тремя рёбрами
(1,2, w=1)
(1,2, w=3)
(1,2, w=5)
будут выданы пути 1-2 (по первому ребру), 1-2 (по второму ребру) и 1-2-1-2 (по первому ребру). Если циклы нежелательны - придётся возиться дольше