найти, существует ли путь определенной длины в ациклическом графе

Я не знаю, будет ли это быстрее, чем подход DFS, но это даст выполнимое решение:

Представьте граф в виде матрицы A и вычислите A^L - путь длины L между i и j существует тогда и только тогда, когда A[i][j] != 0

Кроме того, что касается решения DFS: вам не нужно находить все пути в DFS — вам следует ограничиться путями длиной ‹= L, и тем самым обрезать некоторые поисковые запросы. , как только длина превысит необходимую длину. Вы также можете избежать поиска, когда путь длины L достигает цели.

Другой возможной оптимизацией может быть двунаправленный поиск.

• Найдите все вершины, у которых есть путь длины L/2 от источника до них.
• Затем найдите все вершины, у которых есть пути длины L/2 от них к цели (DFS на обратном графе)
• Затем проверьте, есть ли общая для обоих наборов вершина, если есть — вы получили путь длины L от источника к цели.

Поскольку граф ацикличен, вы можете упорядочить вершины топологически. Назовем начальную вершину А и конечную вершину В.

Теперь запускается основной алгоритм: для каждой вершины посчитайте все возможные расстояния от A до этой вершины. В начале есть один путь из A в A с нулевой длиной. Затем возьмите вершины в топологическом порядке. Когда вы выбираете вершину x: посмотрите на каждого предшественника и обновите здесь возможные расстояния.

Это должно выполняться за время O(N^3).

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

Я считаю, что вы можете использовать следующий алгоритм, чтобы найти самый длинный путь в дереве. Это предполагает, что ваш график подключен, если это не так, вам нужно будет повторно запустить это для каждого подключенного компонента:

1. Выберите произвольный узел, A.
2. Выполните BFS (или DFS) из A, чтобы найти узел в дереве, самый дальний от A, назовите этот узел B.
3. Выполните BFS (или DFS) из B, чтобы найти узел в дереве, самый дальний от B, назовите этот узел C.
4. Путь от B до C — самый длинный путь в дереве (возможно, связанный для самого длинного).

Очевидно, что если этот путь длиннее L, то его можно сократить, чтобы найти путь длины L.