Самый длинный путь по взвешенному неориентированному графику

Question

Я знаю, что это экспоненциально. Я уже реализовал метод поиска кратчайшего пути с использованием алгоритма Дейкстры. Возможно ли изменить метод, чтобы найти самый длинный путь? Если я сделаю все веса отрицательными, это не должно работать. Все веса на моем текущем графике положительны. Также не должно быть повторяющихся путей.

Я знаю, что алгоритм Bellman Ford работает с отрицательными весами, но я надеюсь, что могу просто изменить свой существующий метод кратчайшего пути.

Answer 1

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

Выполнение всех отрицательных и отрицательных весов Dijkstra сделает бесконечный цикл. Это на самом деле эквивалентно тому, что я только что объяснил выше.

Для получения дополнительной информации, я предлагаю вам прочитать о них: http://en.wikipedia.org/wiki/Topological_sorting http://en.wikipedia.org/wiki/Travelling_salesman_problem

Удачи!