Всем привет. Если у кого есть ссылки на готовые реализации поиска критического пути (самый длинный путь) в неориентированном графе плиз киньте ссылку. Язык не имеет значения. Ссылки на описание алгоритма не интересуют (да копи-паст и не имеет значения). Гугль не помог. Спасибо.
Butters Как раз зависит от реализации. Поэтому имеет значение код. В моём понимании критический путь только один - когда ветвление выполняется не на начало уже определённого в графе элемента. В случае с x86 это например ветвление не на начало инструкции, таким образом одна инструкция является частью другой.
Butters Граф взвешенный? Отрицательные веса присутствуют? Если отрицательных весов нет, то достаточно найти реализацию Дейкстры и развернуть priority queue и операцию сравнения расстояния. P.S. Не слушайте Clerk. У него узконаправленное мышление и собственная терминология.
Butters Извиняюсь. Прогнал. Недостаточно... На графах с положительными циклами получится то же, что Дейкстра на графах с отрицательными циклами.
Граф задан матрицей смежности, невзвешен. Про переделку поиска минимального пути знаю, но что-то ничего толком не вышло поэтому и запостил тут и еще на паре форумов. К удивлению не увидел ни одного решения для неориентированных графов (м.б. плохо искал). В качестве примера матрица смежности выглядит так 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 имеется цикл Пост Clerk'a понял, он свел его в низкоуровневое программирование вирусных движков, лоадеров и т.д., что мне в данном случае не нужно
Butters Ну так форум ведь не батаников, а кодеров. И не вобще свёл, а только пример привёл. Граф ведь не только содержит инфу типо векторов, она зависит от реализации поймите.)
Butters Я чего-то не понимаю или для невзвешенного графа с циклами решением будет ответ: критический путь бесконечен.
l_inc Ок, я действительно неправильно сформулировал, извините. Все пути имеют одинаковый вес, допустим 1. Необходимо найти узел, выйдя из которого можно пройти максимальное количество узлов, не посещая узлы более 1 раза. Дейкстра даст на вышеприведенном графе как вы уже сказали конечно бесконечный цикл. Задача имеет сугубо теоретический интерес, крепко засела в голове. Понятный ликбез на эту тему мне бы не помешал.
Если я правильно понял, это задача нахождения Гамильтонова графа, реализовать можно с помощью Boost Graph Library.
TSS Максимального гамильтонова пути, если быть точным. А если уж совсем точным, то это частный случай задачи коммивояжёра, которую качественно круче чем в лоб всё равно не решить (NP).
Блин... постоянно забываю, что граф невзвешенный. Просто гамильтонова пути... да и гамильтоновым он тоже быть не обязан... И тогда соответственно коммивояжёр тут не совсем причём. Хотя похоже в любом случае задача остаётся NP.
