Najkrótsza ścieżka bywa łatwa, najdłuższa — dramatycznie trudniejsza
W grafie znalezienie najkrótszej drogi jest klasycznym problemem z wydajnymi algorytmami: dla nieujemnych wag działa algorytm Dijkstry, a w grafie nieważonym wystarcza BFS. Bardzo podobnie brzmiący problem znalezienia najdłuższej prostej ścieżki — bez powtarzania wierzchołków — jest w ogólnych grafach NP-trudny. Różnica bierze się z warunku „prosta”. Bez niego dodatni cykl pozwalałby dowolnie wydłużać drogę przez krążenie w kółko. Z warunkiem zakazu powtórzeń trzeba wybierać globalnie, które wierzchołki wykorzystać i w jakiej kolejności, a problem zawiera w sobie ścieżkę Hamiltona jako przypadek szczególny.
Najkrótsza droga ma strukturę, którą można wykorzystywać
W problemie najkrótszej ścieżki działa zasada optymalności: fragment najkrótszej drogi także musi być najkrótszym odpowiednim fragmentem, inaczej można by podmienić go na lepszy i skrócić całość. Algorytmy takie jak Dijkstra wykorzystują tę strukturę przy nieujemnych wagach, stopniowo ustalając odległości. W grafach nieważonych BFS robi to jeszcze prościej warstwami. To nie znaczy, że każdy wariant shortest path jest łatwy, ale standardowe wersje mają efektywne algorytmy.
Dlaczego „najdłuższa” nie jest lustrzanym odbiciem
Gdyby wolno było powtarzać wierzchołki, graf z dodatnim cyklem nie miałby skończonej najdłuższej trasy: można byłoby obiegać cykl dowolnie wiele razy. Dlatego sensowny problem longest path zwykle wymaga ścieżki prostej. Ten zakaz niszczy lokalną swobodę. Wejście na jeden wierzchołek może zablokować lepszą możliwość później, a decyzje z początku ścieżki wpływają na całą resztę.
Hamilton ukryty w najdłuższej ścieżce
Jeżeli graf ma n wierzchołków, ścieżka Hamiltona odwiedza wszystkie dokładnie raz, więc ma n−1 krawędzi. Gdybyśmy umieli w czasie wielomianowym znajdować najdłuższą prostą ścieżkę w dowolnym grafie, moglibyśmy sprawdzić, czy jej długość wynosi n−1 i tym samym rozwiązać problem ścieżki Hamiltona. Ponieważ ten problem jest NP-zupełny, longest path jest NP-trudny. To czysty przykład redukcji: trudność jednego zadania zostaje osadzona w drugim.
Są wyspy łatwości
NP-trudność dotyczy grafów ogólnych. Dla pewnych ograniczonych klas sytuacja się zmienia. Na przykład w skierowanych grafach acyklicznych najdłuższe ścieżki można obliczać wydajnie dzięki porządkowi topologicznemu. To ważna lekcja: klasyfikacja problemu zawsze zależy od dokładnych warunków wejścia. Dodanie struktury może usunąć źródło kombinatorycznej eksplozji.
Jedno słowo w specyfikacji może zmienić klasę problemu
„Najkrótsza” i „najdłuższa” wydają się matematycznie symetryczne, ale algorytmicznie nie muszą być. Najważniejsze nie jest brzmienie celu, tylko to, jakie własności umożliwiają bezpieczne decyzje lokalne i jakie zależności globalne tworzą ograniczenia. W projektowaniu algorytmów precyzja specyfikacji potrafi być różnicą między prostym rozwiązaniem a problemem z rdzeniem NP-trudności.
Dlaczego nie wystarczy odwrócić znaków wag
Kusi, by najdłuższą ścieżkę sprowadzić do najkrótszej przez zamianę każdej wagi w jej wartość przeciwną. Dla grafów ogólnych nie rozwiązuje to problemu najdłuższej prostej ścieżki. Po zmianie znaków pojawiają się ujemne cykle, a standardowe zagadnienie shortest path przestaje odpowiadać warunkowi „nie odwiedzaj wierzchołka ponownie”. Problem najdłuższej ścieżki jest trudny właśnie przez globalny zakaz powtórzeń. W DAG-ach sytuacja jest inna: cykli nie ma, więc porządek topologiczny pozwala obliczać zarówno najkrótsze, jak i najdłuższe ścieżki w czasie liniowym względem rozmiaru grafu. Ten kontrast pokazuje, że czasem to obecność cykli i związane z nimi globalne wybory są prawdziwym źródłem trudności.