Блог пользователя sergileon

Поиск k кратчайших путей ориентированном графе.
Автор sergileon, история, 9 лет назад, По-русски

Требуется найти k кратчайших путей в ориентированном графе от одной вершины до другой (обе вершины заданы). Веса положительные. N < 1000, M = n * 4, k = 10. Может знает кто-нибудь, как решить данную задачу? Пока мои размышления свелись к следующему: найти первый кратчайший путь Дейкстрой, затем искать следующие пути без одного ребра из найденного пути. Так получится найти второй путь. А дальше тупик.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Можно сделать примерно такое: посчитать k кратчайших путей до каждой вершины. Запускаем что-то типа Дейкстры, в котором для каждой вершины вычисляем k кратчайших расстояний. Для каждой пары (вершина, номер кратчайшего пути в порядке увеличения длины) находим длину кратчайшего пути и предка — такую же пару (вершина, номер кратчайшего пути), из которой мы попали в текущую вершину. Ну и если это делать с помощью очереди с приоритетом или сета, то у нас будет сет с nk элементами, которые в сумме будут обработаны за О(mk2) времени (k раз обрабатываем все m ребер, при этом для каждого ребра пересчитывается O(k) расстояний). Итого вроде O(nklog(nk) + mk2) времени, должно зайти.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

а требуется найти сами пути? или только их длины?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем sergileon (предыдущая версия, новая версия, сравнить).

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Наверное, это тебе поможет: https://en.wikipedia.org/wiki/Yen%27s_algorithm

→ Ответить