Ścieżka o największym koszcie w grafie ważonym

Question

Mam wydaje mi się, że ciekawy problem. Dużo uczy się algorytmów do najkrótszych / o najmniejszym koszcie scieżek, np BFS czy Dijkstra. Ale ostatnio zainteresowałem się najdłuższymi scieżkami, problem, gdzie krawędzie mają wagi jeden, i trzeba znaleźć najdłuższą scieżkę w takim grafie, już sobie z nim poradziłem: dzielę graf na SCC, wrzucam na kolejkę, z których nie wychodzą już żadne, mam licznik ile wychodzi krawędzi z każdego wierzchołka, i jak przetwarzam wierzchołek to idę po wszystkich krawędziech, którego do niego idą, i odejmuję jeden. I tak w kółko jak nic nie wychodzi to wrzucam na kolejkę, aktualizuje ile wchodzi..... - dynamik. Chodzi mi o to co jest w tym zadaniu: https://atcoder.jp/contests/dp/tasks/dp_g , tylko w tym zadaniu nie trzeba dzielić na SCC, bo nie ma cykli.

Zastanawiam się jak znaleźć ścieżkę o największym koszcie, intuicyjne wydaje się, żeby zrobić Dijkstrę, tylko zamiast od najmniejszych iść do największych, tylko nie wiem czy to jest dobre. Bo teorytycznie wydaje mi się, że na podobnej zasadzie jak w algorytmie Dijkstry, będziemy mieć pewność, że jest to ścieżka o największym koszcie. Więc mam pytania:

1- czy to jest dobre

2 - Czy da się to zrobić w złożonności szybszej niż Dijkstra?

Z góry dziękuję za pomoc i poświęcony czas!

edit: oczywiście zakładam, że po każdej krawędzi można przejść maksymalnie raz, bo tak to byśmy sobie w kółko chodzili i zrobili koszt nieskończoność.

3 - czy algorytmy najdłuższch / o największym koszcie pojawiają się w zadaniach?, bo ja np. jeszcze nigdy się z czymś takim nie spotkałem, oprócz tego z Atcodera.

Comments

tylko z tą Dijkstrą od największych to wsm mam taki problem, że ciężko stwierdzić kiedy już w danej ścieżce szedłem przez dany wierzchołek, bo w Dijkstrze naturalnie to omijaliśmy, bo to niepotrzebnie podbijało wynik.

---

@pasjonat_algorytmiki, 

I teraz to się już wsm zastanawiam, czy nie można zrobić tego samego co w tym, gdzie krawędzie mają wagi 1.

---

Na 90% wydaje mi się, że trzeba zrobić to samo co w tym zadaniu z atcodera, tylko brać pod uwagę krawędzie. Ale nie jestem pewien

Answer 1

Nawet jeśli graf nie będzie ważony to znalezienie najdłuższej ścieżki z wierzchołka jest w zasadzie równoważne znalezieniu ścieżki Hamiltona co jest NP-zupełne, czyli nie da się tego rozwiązać w czasie wielomianowym.

Przykład dla którego Dijsktra nie działa

Natomiast jest inne ciekawe zadanie. Znajdź najdłuższą ścieżke w drzewie. Do tego jest bardzo proste i przyjemne rozwiązanie

Comments

No wsm tak ten case co gość opisał na stacku kończy moje próby zrobienia tego Dijkstrą....

Wydaje mi się, że rozwiązanie jest takie, że idziesz sobie jakimś DFS-em(z dowolnego wierzchołka) do dowolnego wierzchołka, który jest ostatni na skraju(bez sensu zacząć z nie będącego ostatnim na skraju, bo wtedy odległość będzie mniejsza) i z takiego obojętnie jakiego wierzchołka puszczamy DFS-a, który znajdzie najdłuższą ścieżkę, i to jest wynik. Przypomniałem sobie o zadaniu, taksamo z tych eliminacji EJOI 2020, po 14 OIJ i tam trzeba było znaleźć długość takiej najdłuższej ścieżki i jeszcze policzyć ile ich jest. Z tym policzeniem już mam problem i nie wiem jak to zrobić. Dasz jakiegoś hinta?

---

Tak. Jeśli ten wierzchołek "ostatni na skraju" to najbardziej oddalony wierzchołek od źródła to tak się to robi. Jak trzeba liczyć ile ich jest to dp na drzewie