Algorytm Dijkstry

Tutorial
Na ten temat mamy również tutorial „Algorytm Dijkstry”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
Algorytm Dijkstry animacja (1) Wykonanie algorytmu na przykładzie
REKLAMA

Czysty kod. Podręcznik dobrego programisty
−40%41,40 zł
Algorytmy
69,00 zł

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.
Ocena: +10 Tak Nie
Liczba głosów: 10.

Dodano: 17 marca 2017 15:07, ostatnia edycja: 26 stycznia 2019 17:49.

REKLAMA

Zobacz też

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.

→ Czytaj całość

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość

Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.

Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).

Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.

→ Czytaj całość
Polityka prywatnościKontakt