Как найти кратчайший путь длины k от вершины во взвешенном графе?

Question

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

Мне кажется, что алгоритм Джикстры не подходит для этой задачи, поскольку мы не можем выбрать размер пути.

Имеется ли алгоритм для решения этой проблемы?Может ли вариант алгоритма Джикстры добиться цели?

Например, для следующего графика ( Пример графика ).При k = 3 для вершины A мы бы назвали путь, подобный AEDC, с весом 324. Это путь с минимальным весом.

Answer 1

Нет, я не думаю, что Диджакстра преуспеет.Вы не ищете пути к каждому узлу с наименьшим расстоянием, вы хотите получить в любом месте (то есть k прыжков от вашего источника) с минимальным расстоянием.

Вы можетевместо этого используйте обход графа в ширину или в глубину и просто найдите минимальное расстояние в дереве поиска, ограниченное k.Вы можете использовать ответвление и ограничение для оптимизации поиска по дереву.

Answer 2

Если график действительно завершен , как вы упомянули в вопросе, то это пример проблемы суммы подмножеств

https://en.wikipedia.org/wiki/Subset_sum_problem

Поскольку complete graph позволяет вам переходить с любого узла на любой узел в любое время, когда структура графика не имеет значения, только веса.Проблема в NP-полная , хотя нет эффективного способа сделать это

Если график не является полным, то ответ Берги необходим.Дорогой BFS - ваш единственный выбор