DWIE najkrótsze ścieżki w grafie

Witam, piszę aby poradzić się co poniektórych jak znaleźć dwie najkrótsze ścieżki w grafie. Problem właśnie w tym że potrzebuję znaleźć dwie a nie jedną gdzie sprawa była by prosta. Nie bardzo wiek jak to skutecznie zrobić, pomysłów mam kilka, ale chyba żaden nie jest właściwy - przynajmniej nie w takiej formie. Zdaje sobie sprawę, że nie działają, ale może coś gdzieś blisko jestem.

Nie ma ujemnych wag.

Jeden jest taki żeby po odnalezieniu ścieżki przy pomocy dijkstry nie przerywać szukania, tylko docelowy wierzchołek odstawić do zbioru wierzchołków wolnych i kontynuować.

Kolejny jest taki, żeby wierzchołkom, które zawierają się w najkrótszej ścieżce ustawić flagi =odwiedzony a wszystkim w kolejce zapamiętywać odległości do początku, i po odnalezieniu ścieżki cofać się do wierzchołka początkowego odrzucając nie najkrótsze ścieżki różne od znalezionej aż do osiągnięcia wierzchołka początkowego.

Ten drugi być może i działa, ale nie wiem jak by wyszło ze złożonością.

Czy ktoś jest w stanie coś poradzić?

Jak znajdziesz najkrótszą ścieżkę, która składa się z k krawędzi, to potem szukasz najkrótszej ścieżki w k grafach, z których każdy kolejny różni się od tego zadanego tym, że nie ma jednej krawędzie. Złożoność będzie k razy większa niż gdyby szukać tylko najkrótszej. Nie wiem, czy to najlepszy pomysł, ale taki mi przychodzi do głowy i powinien teoretycznie zadziałać.

No to prawie Brute-Force ;) może jednak jest coś bardziej optymalnego...

Co dokładnie rozumiesz przez "dwie najkrótsze ścieżki".

Te ścieżki:
a)mają różne wszystkie wierzchołki
czy
b)mają różne wszystkie krawędzie
czy
c)różnią się przynajmniej jedną krawędzią

c)

Rozwiązanie najprostsze(ale pewnie są też szybsze):

Znajdujesz za pomocą Dijkstry najlepszą ścieżkę(nie tylko wartość).
Musisz użyć Dijkstry, która pamięta najlepszą ścieżkę( http://en.wikipedia.org/wiki/Dijkstra's_algorithm )

Później usuwasz z grafu/oznaczasz jako zakazaną pierwszą z krawędzi z najlepszego rozwiązania i zapuszczasz Dijkstrę.
Następnie ponownie wstawiasz do grafu tą krawędź którą usunąłeś, a usuwasz drugą z najlepszego rozwiązania i znowu zapuszczasz Dijkstrę.
itd. dla każdej krawędzi z optymalnego rozwiązania.

Na samym końcu wybierasz najlepsze z tych rozwiązań.

best_route =  Dijkstra(graph);
second_best_route.setRouteLength(+infinity);

for (i=0;i<best_route.length() - 1,i++)
{
   graph.delEdge(new Edge(best_route[i],best_route[i+1]));
   tmp_route= Dijkstra(graph);
   if (tmp_route.routeLength() < second_best_route.routeLength())
      second_best_route=tmp_route;
   graph.addEdge(new Edge(best_route[i],best_route[i+1]));
}

if (second_best_route.routeLength() == +infinity) throw new OnlyOneRouteException();
return second_best_route;

Koszt to oczywiście O(koszt Dijkstry*długość optymalnego rozwiązania)

No to właśnie o tym mówił Chodnik... to prawie jak Brute Force, bardzo słabe rozwiązanie. Z całą pewnościa wolne i na pewno są lepsze.

OK, już sobie poradziłem. Zostało na Dijkstrze i zapamietywaniu dwoch odleglosci w wierzcholku.

Witam!
Ja mam ten sam problem do rozwiązania :D więc podbijam stary temat, który niestety mi nie bardzo pomógł :(

e2rd napisał(a)

Witam!
Ja mam ten sam problem do rozwiązania :D więc podbijam stary temat, który niestety mi nie bardzo pomógł :(
No ale czego nie rozumiesz ?
Najpierw wyznaczasz najkrótszą ścieżkę. Później wyjmujesz z grafu pierwszą krawędź tej najlepszej ścieżki i szukasz w tak zmodyfikowanym grafie najkrótszą ścieżkę (zapamiętujesz ją). Później wkładasz z powrotem wyjętą krawędź, a wyrzucasz drugą i znowu szukasz najkrótszej ścieżki (zapamiętujesz ją) itd. Na koniec wybierasz najkrótszą z zapamiętanych ścieżek i to jest ta duga co do długości. Pierwszą znalazłeś na samym początku.

Przede wszystkim jest to rozwiązanie mało wydajne a po drugie nie rozwiązuje wszystkich przypadków.
http://img175.imageshack.us/my.php?image=graffn0.png
Dla tego grafu rozwiązanie z usuwaniem krawędzi znajdzie tylko jedną ścieżkę. Nie uwzględniając takiej:
-dół, prawo, dół, lewy-górny, dół, dół
Pozdrawiam

Hehe, świetny kontrprzykład :]

A jakby przerobić dijkstre, żeby pamiętała dla każdego wierzchołka 2 wartości (minimalną i drugą minimalną) i 2 poprzedniki ?

e2rd napisał(a)

Przede wszystkim jest to rozwiązanie mało wydajne
Pytanie - jak bardzo tej wydajności potrzebujesz ? Nie wystarczy ?

e2rd napisał(a)

a po drugie nie rozwiązuje wszystkich przypadków.
http://img175.imageshack.us/my.php?image=graffn0.png
Dla tego grafu rozwiązanie z usuwaniem krawędzi znajdzie tylko jedną ścieżkę
Z takim przypadkiem można sobie łatwo poradzić. Bierzesz każdy kolejny wierzchołek najlepszej drogi i szukasz najkrótszej drogi od niego do niego samego. Wybierasz ten wierzchołek, który wypadł najlepiej i wszczepiasz cykl do najlepszej drogi.

W kwestii wyszukiwania k najkrótszych ścieżek w grafie polecam post

http://blog.dotnetwiki.org/2009/01/05/AKShortestPathImplementationInNet.aspx

opisujący algorytm Hoffmana-Pavley'a (Hoffmann-Pavley algorithm), zaimplementowany zresztą w C# w bibliotece QuickGraph jako RankedShortestPathHoffmanPavley.