Algorytm Dijkstry

25.11.2009 - Krzysztof Nowicki
TrudnośćTrudność

Krok algorytmu wygląda tak:

Bierzemy "sąsiada", który jest najbliżej od $ A $ (można w miarę szybko znaleźć takiego sąsiada, jeśli zbiór wszystkich "sąsiadów" trzymamy w kopcu, który pamięta nam element najmniejszy).

Możemy napisać własny kopiec jak również, o ile potrafimy, możemy skorzystać z kopca zawartego w stl-u. Kopiec z stl-a pamięta element największy, a my chcemy odzyskiwać element najmniejszy. Można to obejść na dwa sposoby:
 - (trudniej) pisząc własny operator porównywania (który dla liczby mniejszej mówi, że jest większa)
 - (łatwiej) wrzucając do kopca ujemne wartości odległości od $ A $ (wtedy miasto które będzie najbliżej $ A $ będzie miało najmniejszą co do wartości bezwzględnej odległość do miasta $ A $, zatem jeśli będą to wszystko liczby ujemne, to będzie ona największa z nich, zatem będzie na górze kopca. Trzeba tylko pamiętać, że zabierając wartość z kopca należy znów zamianić ją na dodatnią

Jeśli mamy już takiego najbliższego sąsiada, sprawdźmy jak to co proponuje kopiec ma się do tego, co jest w tabeli odpowiedzi

-Jeśli wartość z kopca jest większa, tzn, że już wcześniej wyciągnęliśmy ten wierzchołek z kopca (z mniejszą propozycją) i nie ma sensu już nic tutaj robić bo już rozważaliśmy ten wierzchołek

-Jeśli jest równa (mniejsza być nie może, licząc każdą propozycję uaktualniamy zapis w tablicy odpowiedzi), to możemy być pewni, że odpowiedź wyliczona dla niego jest poprawna, możemy teraz rozważyć jego bezpośrednich sąsiadów i zdecydować czy należy ich wrzucić do kopca. Wystarczy sprawdzić, czy odległość w tablicy odpowiedzi jest mniejsza od tego co proponuje kopiec. Jeśli tak, to w tablicy odpowiedzi należy uaktualić odległość na mniejszą, i wrzucić to do kopca "sąsiadów".

Zdarzyć się może, że trzymamy w kopcu wiele razy ten sam wierzchołek (zależy od szczegółowej implementacji), po to są w ogóle te dwa sprawdzenia. Wtedy wyciągając go poraz drugi nie ma sensu liczyć dla niego drugi raz czegokolwiek.

 

Nieskończoność

Własnie tutaj korzystamy z tego, że na początku wszystkie miasta dostały "nieskończoność" na odległość od $ A $, jeśli jakies miasto nie było ani razu uwzględnione nadal ma tam "nieskończoność", każda możliwa do uzyskania wartość powinna być od niej mniejsza. Wtedy znajdując ścieżkę o dowolniej długości stwierdzamy automatycznie, że jest krótsza niż "nieskończoność" i dodajemy do zbioru "sąsiadów" nie zastanawiając się nad tym, czy już kiedyś byliśmy w tym mieście, czy nie.

 

Kroki wykonujemy dopóki jeszcze możemy wyciągnąć coś ze zbioru "sąsiadów", po ich wykonaniu otrzymamy w tablicy odległości najkrótsze odległości poszczególnych miast od miasta $ A $ oraz "nieskończoność" dla miast, dla których ścieżka owa nie istnieje.

 

Aby sprawdzić tylko długość najkrótszej ścieżki z miasta $ A $ do miasta $ B $ możemy zakonczyć działanie algorytmu w momencie, w którym $ B $ jest wyjmowany ze zbioru "sąsiadów"  jako element najbliższy, wtedy mamy gwarancję, że obliczony wynik jest wynikiem ostatecznym i poprawnym (co było dowodzone).

3.3
Twoja ocena: Brak Ocena: 3.3 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com