Учитывая взвешенный орграф и весовую функцию , обычно можно использовать алгоритм Дейкстры для получения кратчайшего пути. Что меня интересует, так это как получить -короткий путь, -короткий путь и так далее.
Вопросов:
Существует ли эффективный алгоритм для получения i-го самого короткого пути между двумя узлами во взвешенном графе?
Существует ли эффективный алгоритм для получения k-самых-кратчайших путей между двумя узлами во взвешенном графе?
Ответ на любой из них в порядке, хотя мне интересно, можно ли сделать ответ на второй вопрос более эффективно, чем звонков на ответ на первый вопрос.
algorithms
graphs
shortest-path
graph-traversal
Реал Слав
источник
источник
Ответы:
Если вы запрещаете циклы, вы можете захотеть взглянуть на алгоритм Hershberger et al. [2].
[1] Эппштейн, Дэвид. «Нахождение k кратчайших путей». Журнал SIAM по вычислительной технике 28.2 (1998): 652-673. [ CiteSeerX ]
[2] Гершбергер, Джон, Мэтью Максел и Субхаш Сури. «Нахождение k кратчайших простых путей: новый алгоритм и его реализация». Транзакции ACM по алгоритмам (TALG) 3.4 (2007): 45. [ CiteSeerX ]
источник