[Algorytmy] Znajdowanie najdłuższej drogi w grafie.

lukaszokaj · Post autor: **lukaszokaj** » 8 sie 2012, o 12:36

Czy może ktoś zna takie algorytmy (znajdowania najdłuższej ścieżki w grafie). Jest to jeden z problemów w informatyce, ale są aproksymacyjne algorytmy, które rozwiązują ten problem. Proszę o wymienianie nazw algorytmów, bądź opisanie znanej metody.

bartek118 · Post autor: **bartek118** » 8 sie 2012, o 13:39

A Dijkstra (tyle że w trochę odwrotny sposób) nie zadziała? Trzebaby dopisać tylko wykrywanie cykli jakby miał się algorytm zapętlić.

lukaszokaj · Post autor: **lukaszokaj** » 8 sie 2012, o 14:49

A. Bjӧrklund i T. Husfeldt, wymyślili też pewien, algorytm tylko nie mogę prawie nic znaleźć na ten temat. Może ktoś coś wie, ma.

Zordon · Post autor: **Zordon** » 8 sie 2012, o 15:10

bartek118 pisze:A Dijkstra (tyle że w trochę odwrotny sposób) nie zadziała? Trzebaby dopisać tylko wykrywanie cykli jakby miał się algorytm zapętlić.

nie zadziała z wielu powodów, problem najdłuższej ścieżki w grafie ma status obliczeniowo trudnego. Można go za to efektywnie rozwiązywać w szczególnych przypadkach, np. dla drzewa, lub grafu skierowanego acyklicznego.

lukaszokaj · Post autor: **lukaszokaj** » 8 sie 2012, o 15:19

Algorytm ma zadziałać dla grafów hamiltonowskich, posiadających taką ścieżkę.