Popularne na dworze króla Vizimira powiedzonko głosiło, że jeśli Dijkstra twierdzi, że jest południe, a dookoła panują nieprzebite ciemności, należy zacząć niepokoić się o losy słońca.
Jak dobrze wszystkim wiadomo, Dijkstra prawdę Ci powie, lecz pytanie można mu zadać tylko jedno - "Jaka jest, panie hrabio, najkrótsza ścieżka w grafie (skierowanym bądź nie) o nieujemnych wagach?" Niestety, jak to Sigismund (czy też może Edsger?) ma w swym zwyczaju, odpowiedź otrzymujemy w zawiły sposób. Uczonym językiem można by nazwać to niejakim Algorytmem Dijkstry. Więc pozostawiając wstęp przejdźmy do tego dziwnego szyfru…
Podstawowe informacje
Algorytm Dijkstry
- operuje na grafach ważonych o nieujemnych wagach krawędzi,
- jest algorytmem zachłannym
- wynikowa tablica zawiera długości najkrótszych ścieżek z danego źródła do odpowiednich wierzchołków grafu
- złożoność : naiwna O(V2), kopcowa O(ElogV), hardcorowa - czyli kopiec Fibonacciego O(E+VlogV)
Algorytm
IN :
G(V,E) -> graf (skierowany bądź nie), o V wierzchołkach, E krawędziach
s -> wierzchołek źródłowy
OUT:
d[] -> tablica najkrótszych ścieżek z s do poszczególnych wierzchołków grafu
Zaczynamy od utworzenia tablicy wynikowej d[], w której każdemu elementowi za wyjątkiem źródła przyznajemy wartość teoretycznej nieskończoności, wierzchołkowi s nadajemy wartość '0'. Następnie tworzymy zbiór wierzchołków jeszcze nie przetworzonych Q (najlepiej kolejkę priorytetową, czyli kopiec), za pomocą którego będziemy przeglądać kolejne wierzchołki. Tu właśnie wkracza pazerność (czy też zachłanność) algorytmu dijkstry - najkorzystniejszy jest dla nas wierzchołek o najmniejszym aktualnym koszcie dojścia (czyli minimum z d[]). Jak przetwarzać? Ano, bierzemy sobie takiego delikwenta i porównujemy z sąsiadami - jeżeli koszt dojścia do niego i długość drogi potrzebnej do osiągnięcia sąsiada [ :P ] jest mniejszy niż aktualny koszt sąsiada [ xD ] to poprawiamy koszt dojścia do sąsiada na lepszy. Przetworzonego Pana Wierzchołka ze zbioru wyrzucamy. Powtarzamy tą operację aż do opustoszenia zbioru. Wszystkie najkrótsze ścieżki z wierzchołka s mamy już zapisane w tablicy d[], więc idziemy na pizze :).
Pseudokod
Dijkstra(G,wagi,s): dla każdego wierzchołka v w V[G] wykonaj d[v] := nieskończoność // inicjalizacja tablicy wynikowej d[s] := 0 Q := V // utworzenie zbioru v nieprzetworzonych dopóki Q niepuste wykonaj u := Zdejmij_Min(Q) // przetwarzanie wierzchołków dla każdego wierzchołka v - sąsiada u wykonaj jeżeli d[v] > d[u] + waga(u,v) to d[v] := d[u] + waga(u,v)
