Teoria grafów, maksymalna droga

1

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.

0

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?

0

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ść

0

ok, doprecyzuję:

  • maksymalna droga, czyli droga przechodząca przez jeden wierzchołek max. 1 i suma wag na krawędziach jest największa
1

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 n<sup>2*2</sup>n 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:
L(v,S)=\max_{w\in N(v)\setminus S} d_{vw}+L(w,S\cup{w}) jeśli v != s:
L(v,S)=0 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

0

@JrQ- a ma przechodzić przez wszystkie wierzchołki czy też nie? Bo jak ma, to to jest problem komiwojażera :P

0

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ę.

0

A co jeśli będzie ujemny cykl ?
Możesz zminusować wagi a potem rzeczywiście algorytm ale Belmana Forda.

0
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.

0

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ć).

1 użytkowników online, w tym zalogowanych: 0, gości: 1