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.
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:
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).
Dodano: 17 marca 2017 15:07, ostatnia edycja: 26 stycznia 2019 17:49.
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.
Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.
Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.
Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.