Тема: Longest Path
you are given directed graph without cycles. How to find the longest path in this graph?
2 2010-04-14 12:59:25 Отредактировано brainail (2010-04-14 13:00:30)
Re: Longest Path
Так как нету циклов, то граф ациклический.
1. Делаем топологическую сортировку
2. Пускаем ДП по этому графу, так как рёбра направленны в одну сторону, то ДП будет работать правильно :
F( U ) = MAX( F( V ) + C( U, V ) ), U -> V - некоторое ребро заканчивающееся в U.
Re: Longest Path
В орграфе намного проще.
А в неориентрированом сложнее.... 
Re: Longest Path
coder.ua пишет:
В орграфе намного проще.
А в неориентрированом сложнее....
Спрашивалось конкретно про орграф.
А насчет неориентированного - если по каждому ребру можно проходить сколько угодно раз, то если есть цикл, то и ответ бесконечность. А если циклов нету, тогда там все очевидно.
Если же по каждому ребру (и вершине) можно проходить по 1 разу, то эта задача НП-полная и я не понимаю, к чему было сказано что сложнее - полиномиального алгоритма просто нету.
Re: Longest Path
омг...
Сказано было что для неориентированного дерева сложнее чем для орграфа.
Я не говорил что могут быть циклы и т.п.
Существует решение за О(n) и для такого графа.Но для него реализация сложнее(что я и сказал)
Re: Longest Path
Неужели 2 бфса написать сложнее чем эту динамику? Сомневаюсь...