Witajcie,
mam następujący problem: mam graf skierowany, spójny i potrzebuję znaleźć maksymalną drogę między dwoma wierzchołkami.
Potrzebuję jakiś sensowny algorytm do tego. Myślałem o Dijkstrze, ale chyba się nie nada? Jest jakiś sensowny sposób aby to rozwiązać?
Pozdrawiam, Tomek.
A co to jest "maksymalna droga" w grafie? Droga na której masz maksymalny przepływ? Maksymalną sumaryczną wartość wag? Największą ilość krawędzi?
jeśli Twój algorytm trafi na jakikolwiek cykl z suwą krawędzi w cyklu > 0 to maksymalna droga będzie równa nieskończoność
ok, doprecyzuję:
- maksymalna droga, czyli droga przechodząca przez jeden wierzchołek max. 1 i suma wag na krawędziach jest największa
Na początku myślałem że chodzi Ci o największą ścieżkę powiększającą (w rozumieniu algorytmów wyznaczania max. przepływu), ale wychodzi na to że szukasz tego:
http://en.wikipedia.org/wiki/Longest_path_problem (w przybliżeniu)
Jeśli Twój graf nie jest DAGiem (ew. innym specyficznym), to problem jest, z tego co wiem, NP-trudny.
Jak rozwiązać - mozna to rozwiązać w czasie za pomocą programowania dynamicznego.
Definiujemy:
- L(v, S) jako ścieżkę s->v nie odwiedzająca żadnych wierzchołków w S
- N(v) jako zbiór sąsiadów (wierzchołków połączonych krawędzią z) v.
Teraz zachodzi:
jeśli v != s:
w przeciwnym wypadku
(wiem, tex u nas wygląda odrażająco obecnie)
A najdłuższa ścieżka do v ma długość L(v, {v})
Pomoc w opisie i wzór rekurencyjny skradziony bezczelnie z http://cstheory.stackexchange.com/questions/6025/finding-the-longest-path-between-two-nodes-in-a-bidirectional-unweighted-graph
@JrQ- a ma przechodzić przez wszystkie wierzchołki czy też nie? Bo jak ma, to to jest problem komiwojażera :P
Te definicje w zadaniach są niedopracowane. Spotkałem się z taką, że maksymalna droga to jest najkrótsza droga, która daje maksymalne wartości sumaryczne krawędzi. W takim wypadku wystarczy wziąć wszystkie wagi krawędzi ze znakiem minus i wtedy algorytm Dijkstry puszczony na takim grafie wyznaczy taką drogę.
A co jeśli będzie ujemny cykl ?
Możesz zminusować wagi a potem rzeczywiście algorytm ale Belmana Forda.
maturzysta2013 napisał(a):
A co jeśli będzie ujemny cykl ?
Możesz zminusować wagi a potem rzeczywiście algorytm ale Belmana Forda.
Myślę że jeśli wszystkie wierzchołki są ujemne to problem z ujemnymi cyklami znika bo po prostu wtedy z kolejki priorytetowej zdejmujemy zawsze wierzchołki o największej wadze zamiast o najmniejszej. Tak samo w algorytmie Dijkstry musimy zamienić kierunek relacji przy porównywaniu wagi zastanej wierzchołka z wagą uzyskaną inną drogą pozostawiając większą wagę zamiast mniejszej i wtedy jakakolwiek dłuższa droga naokoło nie pójdzie, bo ona zawsze da mniejszą wagę wierzchołka.
Algorytm Belmana Forda jest rzędu O(V*E) i to by tragicznie wydłużyło czas wykonania programu dla dużych grafów.
Tą metodą nie pójdzie, gdyż druga czynność niweluje pierwszą i wracasz do punktu wyjścia
(wyszłyby ci drogi dla najmniejszych wag, a nie dla największych). Trzeba zrobić tak (bo chyba
nie ma innej możliwości): mamy te wszystkie krawędzie o nieujemnej wadze; bierzemy je teraz ze
znakiem minus i mamy dzięki temu krawędzie o niedodatniej wadze. Teraz przechodzimy przez
wszystkie krawędzie, znajdując liczbę, która jest najmniejszą wagą spośród wszystkich wag
krawędzi w całym grafie. Wartość bezwzględną tej liczby dodajemy do wag wszystkich krawędzi w
tym grafie, otrzymując w ten sposób graf z krawędziami o wagach nieujemnych. Na takim grafie
puszczamy już normalny algorytm Dijkstry, znajdujący najmniejsze wagi (nie musimy tego
algorytmu modyfikować).