Критический путь в неориентированном графе

Тема в разделе "WASM.BEGINNERS", создана пользователем Butters, 3 июн 2010.

  1. Butters

    Butters New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    47
    Всем привет.

    Если у кого есть ссылки на готовые реализации поиска критического пути (самый длинный путь) в неориентированном графе плиз киньте ссылку.
    Язык не имеет значения. Ссылки на описание алгоритма не интересуют (да копи-паст и не имеет значения). Гугль не помог.

    Спасибо.
     
  2. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Butters
    Как раз зависит от реализации. Поэтому имеет значение код.
    В моём понимании критический путь только один - когда ветвление выполняется не на начало уже определённого в графе элемента. В случае с x86 это например ветвление не на начало инструкции, таким образом одна инструкция является частью другой.
     
  3. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Butters
    Граф взвешенный? Отрицательные веса присутствуют?
    Если отрицательных весов нет, то достаточно найти реализацию Дейкстры и развернуть priority queue и операцию сравнения расстояния.

    P.S. Не слушайте Clerk. У него узконаправленное мышление и собственная терминология. :)
     
  4. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Butters
    Извиняюсь. Прогнал. Недостаточно... На графах с положительными циклами получится то же, что Дейкстра на графах с отрицательными циклами.
     
  5. Butters

    Butters New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    47
    Граф задан матрицей смежности, невзвешен. Про переделку поиска минимального пути знаю, но что-то ничего толком не вышло поэтому и запостил тут и еще на паре форумов. К удивлению не увидел ни одного решения для неориентированных графов (м.б. плохо искал).

    В качестве примера матрица смежности выглядит так

    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 понял, он свел его в низкоуровневое программирование вирусных движков, лоадеров и т.д., что мне в данном случае не нужно :)
     
  6. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Butters
    Ну так форум ведь не батаников, а кодеров. И не вобще свёл, а только пример привёл. Граф ведь не только содержит инфу типо векторов, она зависит от реализации поймите.)
     
  7. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Butters
    Я чего-то не понимаю или для невзвешенного графа с циклами решением будет ответ: критический путь бесконечен.
     
  8. Butters

    Butters New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    47
    l_inc
    Ок, я действительно неправильно сформулировал, извините.
    Все пути имеют одинаковый вес, допустим 1.
    Необходимо найти узел, выйдя из которого можно пройти максимальное количество узлов, не посещая узлы более 1 раза.
    Дейкстра даст на вышеприведенном графе как вы уже сказали конечно бесконечный цикл.

    Задача имеет сугубо теоретический интерес, крепко засела в голове. Понятный ликбез на эту тему мне бы не помешал.
     
  9. TSS

    TSS New Member

    Публикаций:
    0
    Регистрация:
    13 апр 2009
    Сообщения:
    494
    Если я правильно понял, это задача нахождения Гамильтонова графа, реализовать можно с помощью Boost Graph Library.
     
  10. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    TSS
    Максимального гамильтонова пути, если быть точным. А если уж совсем точным, то это частный случай задачи коммивояжёра, которую качественно круче чем в лоб всё равно не решить (NP).
     
  11. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Блин... постоянно забываю, что граф невзвешенный. Просто гамильтонова пути... да и гамильтоновым он тоже быть не обязан... И тогда соответственно коммивояжёр тут не совсем причём. :) Хотя похоже в любом случае задача остаётся NP.
     
  12. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Удивительно. http://en.wikipedia.org/wiki/Longest_path_problem
     
  13. Butters

    Butters New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    47
    Stiver
    А теперь внимательно перечитываем первый мой пост.