Тема: Longest Path
you are given directed graph without cycles. How to find the longest path in this graph?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Longest Path
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
you are given directed graph without cycles. How to find the longest path in this graph?
Так как нету циклов, то граф ациклический.
1. Делаем топологическую сортировку
2. Пускаем ДП по этому графу, так как рёбра направленны в одну сторону, то ДП будет работать правильно :
F( U ) = MAX( F( V ) + C( U, V ) ), U -> V - некоторое ребро заканчивающееся в U.
В орграфе намного проще.
А в неориентрированом сложнее....
В орграфе намного проще.
А в неориентрированом сложнее....
Спрашивалось конкретно про орграф.
А насчет неориентированного - если по каждому ребру можно проходить сколько угодно раз, то если есть цикл, то и ответ бесконечность. А если циклов нету, тогда там все очевидно.
Если же по каждому ребру (и вершине) можно проходить по 1 разу, то эта задача НП-полная и я не понимаю, к чему было сказано что сложнее - полиномиального алгоритма просто нету.
омг...
Сказано было что для неориентированного дерева сложнее чем для орграфа.
Я не говорил что могут быть циклы и т.п.
Существует решение за О(n) и для такого графа.Но для него реализация сложнее(что я и сказал)
Неужели 2 бфса написать сложнее чем эту динамику? Сомневаюсь...
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Longest Path