кратчайший путь с указанным количеством ребер

Question

Я ищу алгоритм, который находит кратчайший путь между двумя вершинами (i и j) в графе, который содержит указанное число ребер, n.У меня есть динамическая программа, которая просматривает кратчайший путь к месту назначения с n-1 ребрами, но как я могу быть уверен, что кратчайший путь, который будет найден, начинается с i?

Answer 1

Я предполагаю, что ребра имеют разные затраты / длины и что ограничение состоит в том, что имеется n ребер, и среди всех путей от i до j, которые имеют ровно n отдельных ребер, цель состоит в том, чтобы найти тот, который имеет наименьшую общую стоимость/ длина.

Если вы делаете это с помощью динамического программирования, повторения

spath(f, t, n): --- returns shortest path from 'f' to 't' that has 'n' edges

spath(x, x, 0) = [x] --- path that has only one vertex
spath(x, y, 0) = NO PATH --- when x != y

spath(f, t, n) =
  min cost path over (x is any node that is connected to t):
     spath(f, x, n-1) + [t] (x can be appended because there is edge x - t)

Answer 2

Ваша формулировка неоднозначна. n - это число ребер в графе или количество прыжков в пути? Если последнее, то это уже не самый короткий путь. Если вы имеете в виду первое, то подойдет любой популярный алгоритм кратчайшего пути , такой как Дейкстра. Если вы имеете в виду последнее, то выполните n итераций BFS, начиная с i, и найдите свой j на n-й границе. Если его там нет, то нет пути от i до j в n прыжках. Пройдите через границы BFS, чтобы прочитать ваш путь.