Нахождение k-кратчайшего пути между двумя узлами

9

Учитывая взвешенный орграф и весовую функцию , обычно можно использовать алгоритм Дейкстры для получения кратчайшего пути. Что меня интересует, так это как получить -короткий путь, -короткий путь и так далее.гзнак равноВ,Еd(U,v)2Nd3рd

Вопросов:

Существует ли эффективный алгоритм для получения i-го самого короткого пути между двумя узлами во взвешенном графе?

Существует ли эффективный алгоритм для получения k-самых-кратчайших путей между двумя узлами во взвешенном графе?

Ответ на любой из них в порядке, хотя мне интересно, можно ли сделать ответ на второй вопрос более эффективно, чем звонков на ответ на первый вопрос.К

Реал Слав
источник
2
Поиск в Google по «k кратчайших путей» обнаруживает ряд ссылок, которые описывают алгоритмы для этой проблемы. Также есть статья в Википедии именно на эту тему: en.wikipedia.org/wiki/K_shortest_path_routing
DW
@DW Сделать ответ, с кратким изложением?
Рафаэль

Ответы:

5

ККО(м+NжурналN+К)К

Если вы запрещаете циклы, вы можете захотеть взглянуть на алгоритм Hershberger et al. [2].


[1] Эппштейн, Дэвид. «Нахождение k кратчайших путей». Журнал SIAM по вычислительной технике 28.2 (1998): 652-673. [ CiteSeerX ]

[2] Гершбергер, Джон, Мэтью Максел и Субхаш Сури. «Нахождение k кратчайших простых путей: новый алгоритм и его реализация». Транзакции ACM по алгоритмам (TALG) 3.4 (2007): 45. [ CiteSeerX ]

Юхо
источник