Описание тега longest-path
1
ответ
Вычислительная сложность алгоритма самого длинного пути с рекурсивным методом
Я написал сегмент кода, чтобы определить самый длинный путь в графе. Ниже приведен код. Но я не знаю, как получить вычислительную сложность в этом из-за рекурсивного метода в середине. Так как поиск самого длинного пути - это полная проблема NP, я п…
14 дек '10 в 10:29
0
ответов
Нахождение самого длинного пути в полном ориентированном графе
Я думал о том, как найти максимально длинный путь в полном ориентированном графе для каждой отдельной вершины. Пример такого графика Поэтому для каждой отдельной вершины я хочу найти максимально возможное количество вершин, через которые можно пройт…
28 окт '16 в 11:08
1
ответ
Фундаментальные различия между проблемами "Самый широкий путь" и "Самый длинный путь"
Каковы различия между самыми широкими и самыми длинными путями? Более конкретно, почему первое можно решить, найдя максимальное остовное дерево, а второе - нет. Я знаю, что при составлении максимального связующего дерева сразу становится очевидным, …
12 авг '14 в 23:30
1
ответ
Ошибка индекса вне границ для DAG
Я пишу программу, чтобы найти самый длинный путь для группы доступности базы данных с входными данными из стандартного in. Я, наконец, получил ее для компиляции, сказав, что она использует непроверенные или небезопасные операции из-за моего списка A…
17 апр '16 в 05:16
1
ответ
Найти самый длинный путь в графе, где каждый узел имеет не более двух входящих и двух исходящих ребер
Как видно из заголовка, я должен найти самый длинный путь в ориентированном графе, где каждый узел имеет не более двух входящих ребер и двух исходящих ребер. Я не знаю, поможет ли этот факт чему-нибудь. График будет содержать не более 10000 узлов. И…
30 ноя '16 в 12:58
0
ответов
Алгоритм самого длинного пути с "может" имеет цикл и отрицательный фронт на определенном шаге
Я провел собственное исследование, однако не смог найти правильного решения для своего требования. Проблема в том, что у меня есть грузовик, который должен тратить груз (скажем, мусор). Существуют города (узел) и ребра (путь), которые могут быть пол…
21 дек '17 в 14:35
3
ответа
NetworkX: найдите самый длинный путь в DAG, возвращая все связи на максимум
У меня проблемы с выяснением, как обновить алгоритм networkx dag_find_longest_path(), чтобы он возвращал "N" для связей вместо того, чтобы возвращать первое найденное максимальное ребро, или возвращал список всех ребер, которые связаны для максималь…
09 дек '18 в 23:16
1
ответ
Как найти самый длинный путь в циклическом графе между двумя узлами?
Я уже решил большинство вопросов, размещенных здесь, все, кроме самого длинного пути. Я прочитал статью в Википедии о самых длинных путях, и кажется, что если график был ациклическим, то возникла какая-то легкая проблема, а у меня - нет. Как мне реш…
20 апр '10 в 22:15
1
ответ
Самый длинный путь взвешенного DAG с использованием R igraph
Я реализовал вычисление длинного пути взвешенного DAG с помощью R igraph. Моя реализация (показанная ниже) медленна для больших графиков. Я был бы очень признателен за любые подсказки, чтобы ускорить его. Любые мысли о том, насколько далеко моя реал…
14 ноя '14 в 12:27
1
ответ
Самый длинный маршрут в 2D массиве от макс до мин
Есть 2D массив long[50][50] который заполнен случайными числами от 0 до 100. Мне нужно найти самый длинный путь от самого большого (или первого самого высокого) до самого маленького. Вы можете двигаться вверх, вниз, влево и вправо. Я нашел, как найт…
24 авг '16 в 16:18
2
ответа
Самый длинный путь для взвешенного ориентированного ациклического графа
Я пытаюсь осмыслить эту проблему, а затем написать для нее код Java. Я знаю, что здесь было какое-то обсуждение, но я не вижу много ответчиков, поэтому я хотел бы повторить вопрос, записав свои мысли, и я надеюсь получить некоторую обратную связь от…
05 дек '12 в 11:31
1
ответ
Найти самый длинный путь между множеством узлов в дереве
Недавно наткнулся на вопрос программирования. Данное дерево может быть недвоичным, может быть одной цепью (или линейной) с N узлами. На входе будет набор из K узлов, обозначенных a1,a2....ak. Я хотел бы найти самые длинные простые пути, которые начи…
09 мар '13 в 04:23
1
ответ
Нахождение самого длинного пути в загадке "Бегущий по лезвию стропа"
Я уже несколько дней пытаюсь решить заархивированную головоломку Software ITA Software, известную как Sling Blade Runner. Суть головоломки заключается в следующем: "Как долго вы можете найти цепочку перекрывающихся названий фильмов, таких как Sling …
05 окт '14 в 23:38
1
ответ
Как найти самый длинный путь в ациклическом ориентированном графе с помощью библиотеки OGDF?
Я новичок в библиотеке OGDF и мне нужно найти самый длинный путь в ациклическом ориентированном графе (я хочу использовать встроенные функции OGDF). Я знаю, что можно найти самый длинный путь, используя алгоритмы кратчайшего пути с отрицательными ве…
02 авг '12 в 22:17
1
ответ
Алгоритм самого длинного пути для назначения слоя
Я работаю над программой для создания организационной структуры компании. Я читал об алгоритме самого длинного пути для наложения вершин, и одна вещь меня беспокоила. Чтение, которое я сделал, предполагает, что график должен быть послойным снизу вве…
24 окт '12 в 14:47
1
ответ
Cypher COLLECT заставляет UNWIND раскручиваться в неправильном порядке
Суть графика: http://gist.neo4j.org/?6182d024325343760cb4 Я хочу получить (самый длинный) путь по порядку, и он будет работать, как и ожидалось, до тех пор, пока я не добавлю инструкцию COLLECT, есть ли что-то, касающееся Cypher и COLLECT, которое я…
17 авг '15 в 15:16
2
ответа
Floyd-Warshall для наибольшего расстояния для ненаправленного графа
Я хочу найти наибольшее расстояние между любыми двумя вершинами взвешенного неориентированного графа, используя алгоритм Флойда-Уоршалла. Для этого я сделал несколько изменений: Я добавляю отрицательные веса вместо положительных. Тогда я узнаю кратч…
28 фев '17 в 04:15
2
ответа
Самый длинный путь в сетке
Для заданной сетки G. Каждая ячейка может содержать числа [0 - 9] включительно или алфавитную букву верхнего регистра (скажем, Z); мы можем начать с верхнего левого угла. Тогда, если номер ячейки, на которой мы находимся, равен a, мы можем позволить…
16 июн '13 в 12:40
2
ответа
Как найти самый длинный простой путь (включая все промежуточные узлы) в ориентированном циклическом графе?
Я искал здесь, как найти самый длинный простой путь в ориентированном циклическом графе (простое значение, что каждый узел посещается только один раз, чтобы избежать бесконечного пути), и нашел такие решения. Однако все такие решения, которые я наше…
14 ноя '14 в 13:10
1
ответ
JGraphT: Ошибка переполнения стека с алгоритмом длинного пути Ляо Вонга?
Я пытаюсь реализовать алгоритм самого длинного пути в Java с jGraphT, но я получаю java.lang.StackruError, когда я компилирую. Сообщение об ошибке указывает на строку, куда я копирую график, и на строку, где метод вызывает себя внутри алгоритма. Опи…
03 авг '13 в 10:06