networkx: эффективно найти абсолютный самый длинный путь в орграфе

Я хочу, чтобы networkx нашел самый длинный путь в моем направленном ациклическом графе.

Я знаю о Беллмане-Форде, поэтому я отменил длины графиков. Проблема: networkx 's bellman_ford () требует исходного узла. Я хочу найтиабсолютный самый длинный путь (или самый короткий путь после отрицания), а не самый длинный путь от данного узла.

Конечно, я мог бы запустить bellman_ford () на каждом узле графа и отсортировать, но есть ли более эффективный метод?

Из того, что ячитать (например,http://en.wikipedia.org/wiki/Longest_path_problemЯ понимаю, что на самом деле не может быть более эффективного метода, но мне было интересно, есть ли у кого-нибудь какие-либо идеи (и / или они доказали P = NP (ухмылка)).

РЕДАКТИРОВАТЬ: все длины ребер в моем графике +1 (или -1 после отрицания), поэтому метод, который просто посещает большинство узлов, также будет работать. В общем, победилКонечно, можно посетить ВСЕ узлы.

РЕДАКТИРОВАТЬ: ОК, я только что понял, что мог бы добавить дополнительный узел, который просто соединяется с каждым другим узлом в графе, а затем запустить bellman_ford из этого узла. Любые другие предложения?

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

Ваш ответ на вопрос