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

Проблема: учитывая взвешенный направленный ациклический граф (DAG) и исходную вершину s в нем, найдите наибольшие расстояния от s до всех других вершин в данном графе. Найдите справочную диаграмму: ссылка Зачем нужна топологическая сортировка?...

Я знаю, что в NP-HARD есть следующая проблема: задан простой граф G=(V,E), две вершины v, v' в V, целое число B и неотрицательная функция длины len: E->Z+ , существует ли простой путь из v в v' длины меньше B? Мой вопрос: при тех же условиях,...

Я ищу алгоритм для поиска самого длинного пути между двумя точками в сетке с дополнительным ограничением, что вы не можете повторно посетить ячейку в сетке. (Кроме того, вы можете двигаться только вверх, вниз, влево и вправо). Учитывая эти...

Я знаю, что для неориентированного графа эта проблема является NP-полной, поэтому мы должны использовать грубую силу, чтобы проверить все возможные пути. Как мы можем это сделать? Пожалуйста, предложите псевдокод и расскажите мне о сложности этого...

Я пытаюсь создать скрипт Python, который дает мне самый длинный повторяющийся символ в заданной матрице (по горизонтали и вертикали). Пример: У меня есть эта матрица: afaaf rbaca rlaff При подаче этой матрицы на вход должно...

Дано: невзвешенный направленный граф (G=(E,V)), который может содержать любое количество циклов. Цель: для всех вершин мне нужен самый длинный простой путь к некоторой целевой вершине X в V. Идея алгоритма: For each v in V...

Я пытаюсь получить самый длинный подсписок в списке. Мне нужно правило, которое рекурсивно просматривает список списков и определяет, какой из списков имеет наибольшую длину. Например: ввод: [[1],[1,2],[],[1,2,3,4],[5,6]] вывод: [1,2,3,4]...

Я использую этот код https://www.geeksforgeeks.org/longest-path-undirected-tree/ , чтобы найти самый длинный путь в неориентированном графе. Код использует два раза поиск BFS, чтобы найти самый длинный путь, а затем выводит начало и конец пути и...