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

Я хотел бы найти путь фиксированной длины (заданный при запуске программы) в неориентированном графе. Я использую матрицу смежности моего графа.
Я пытался использовать некоторые алгоритмы, такие как DFS или A *, но они возвращают только кратчайший путь.

Узлы не могут быть снова посещены.

Итак, допустим, что у моего графа 9 узлов, а кратчайший путь состоит из 4 узлов.
Я хочу иметь дополнительную переменную, которая будет "сообщать" алгоритм, который я хочу найти путь, который имеет 7 узлов (например), и он будет возвращать узлы, которые включены в мой ожидаемый путь {1,2,4,5,6,7,8}.
Конечно, если нет никакого решения для пути, который я хочу, он ничего не возвратит (или он вернет путь, близкий к моим объяснениям, скажем, 19 вместо 20).

Кто-то говорил о DFS с возвратом, но я ничего об этом не знаю.
Может кто-нибудь объяснить, как использовать DFS с возвратом или порекомендовать некоторые другие алгоритмы для решения этой проблемы?

Ответы на вопрос(5)

void dfs(int start, int hops)
{
  if(hops == k && start == t)
    {
      path++;
      return;
    }
  else if(hops >= k)
    return;
  for(int w = 1; w <= n; w++)
    if(routes[start][w])
      dfs(w, hops + 1);
}

Здесь k - длина пути, а route [] [] - матрица смежности графа. путь является глобальной переменной. Это может учитывать циклы - это учитывает ВСЕ пути заданной длины. С главной звоните

path = 0;
dfs(source, k);
cout<<path;

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

Гамильтонова проблема цикла, учитывая эффективный алгоритм решения Вашей проблемы.

Следовательно, решения за полиномиальное время не существует (если только P = NP). Для исчерпывающего поиска, экспоненциального решения по времени, проверьте ответ @ amit.

чтобы рекурсивно найти путь необходимой длины.

Код Псуэдо:

DFS(depth,v,path):
  if (depth == 0 && v is target): //stop clause for successful branch
       print path
       return
  if (depth == 0): //stop clause for non successful branch
       return
  for each vertex u such that (v,u) is an edge:
       path.append(v) //add the current vertex to the path
       DFS(depth-1,u,path) //recursively check all paths for of shorter depth
       path.removeLast() // clean up environment

Вышеуказанный алгоритм сгенерируетall дорожки необходимой глубины.
вызов сDFS(depth,source,[]) (где[] это пустой список).

Замечания:

The algorithm will generate paths that might not be simple. If you need only simple paths - you also need to maintain visited set, and add each vertex when you append it to the found path, and remove it when you remove it from the path. If you want to find only one such path - you should return value from the function, (true if such a path was found), and break the loop (and return true) when the return value is true.

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

вы можете найти путь длины d в графе, тогда вы можете запустить этот алгоритм | V | раз и найти самый длинный путь, который NP-полный. Таким образом, вы можете попробовать следующий подход -

1) алгоритм аппроксимации 2) метод грубой силы (больше подходит для программирования). Используйте графический процессор для ускорения вашего кода.

Также вам может быть интересно, что -

существует линейный алгоритм времени для DAG.

ВАШ ОТВЕТ НА ВОПРОС