Algorytm Dijkstry
Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.
Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.
Opis działania algorytmu
W trakcie wykonywania algorytmu dla każdego wierzchołka zostają wyznaczone dwie wartości: koszt dotarcia do tego wierzchołka oraz poprzedni wierzchołek na ścieżce. Na początku działania algorytmu dla wierzchołka źródłowego koszt dotarcia wynosi 0 (już tam jesteśmy), a dla każdego innego wierzchołka nieskończoność (w ogóle nie wiemy, jak się tam dostać). Wszystkie wierzchołki na początku znajdują się w zbiorze Q (są to wierzchołki nieprzejrzane). Następnie algorytm przebiega następująco:
- Dopóki zbiór Q nie jest pusty:
- Pobierz ze zbioru Q wierzchołek o najmniejszym koszcie dotarcia. Oznacz go jako v i usuń ze zbioru Q.
- Dla każdej krawędzi wychodzącej z wierzchołka v (oznaczmy ją jako k) wykonaj następujące czynności:
- Oznacz wierzchołek znajdujący się na drugim końcu krawędzi k jako u.
- Jeśli koszt dotarcia do wierzchołka u z wierzchołka v poprzez krawędź k jest mniejszy od aktualnego kosztu dotarcia do wierzchołka u, to:
- Przypisz kosztowi dotarcia do wierzchołka u koszt dotarcia do wierzchołka v powiększony o wagę krawędzi k.
- Ustaw wierzchołek v jako poprzednik wierzchołka u.
Złożoność czasowa
Oznaczmy liczbę wierzchołków przez n, a liczbę krawędzi przez e. Każda krawędź będzie analizowana jeden raz w przypadku grafu skierowanego lub dwa razy w przypadku grafu nieskierowanego. Oprócz analizy krawędzi w trakcie wykonywania algorytmu n razy przeszukuje się zbiór Q. W przypadku przechowywania zbioru Q w zwykłej tablicy wyszukanie wierzchołka odbywa się w czasie liniowym (O(n)). Wówczas złożoność czasowa algorytmu to O(n2+e). Biorąc pod uwagę, że w przypadku braku krawędzi wielokrotnych liczba krawędzi jest zawsze mniejsza od n2, można powiedzieć, że złożoność czasowa algorytmu to O(n2).
Jeśli zbiór Q będziemy przechowywać w postaci kopca, wyszukiwanie elementu będzie się odbywało w czasie O(logn). Jednak po każdej zmianie kosztu dotarcia do wierzchołka trzeba przebudować kopiec, co również odbywa się w czasie O(logn). Złożoność obliczeniowa algorytmu wyniesie wówczas O(elogn). Dla grafów rzadkich (liczba krawędzi mniejsza pod względem rzędu wielkości od n2/logn) jest to zatem rozwiązanie szybsze, ale dla grafów gęstych – wolniejsze.
Jeśli do przechowywania zbioru Q zastosujemy kopiec Fibonacciego, złożoność obliczeniowa algorytmu zmniejszy się do O(nlogn+e).
Bibliografia
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Liczba głosów: 13.
- Algorytm Bellmana-Forda
- Algorytm Dijkstry
- Algorytm Floyda-Warshalla
- Algorytm Johnsona
Dodano: 17 marca 2017 15:07, ostatnia edycja: 26 stycznia 2019 17:49.
Zobacz też
Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.
Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.
Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.
Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.
Kolejka (ang. Queue) – struktura danych, w której elementy pobierane są z początku, a dodawane na końcu. Z kolejki można zatem pobrać tylko ten element, który był dodany najwcześniej. Kolejka bywa określana również jako kolejka FIFO (z ang. First In, First Out), w odróżnieniu od kolejki LIFO, czyli stosu.
Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.
W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:
Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:
Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.
Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.