algorytm.org

Algorytm Dijkstry

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Dijkstry
Ocena użytkowników:***** / 82
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 09 sierpnia 2005 21:13

Algorytm Dijkstry służy do wyznaczania najmniejszej odległości od ustalonego wierzchołka s do wszystkich pozostałych w skierowanym grafie, w odróżnieniu jednak od Algorytmu Forda-Bellmana, graf wejściowy nie może zawierać krawędzi o ujemnych wagach.
W algorytmie tym pamiętany jest zbiór Q wierzchołków, dla których nie obliczono jeszcze najkrótszych ścieżek, oraz wektor D[i] odległości od wierzchołka s do i. Początkowo zbiór Q zawiera wszystkie wierzchołki a wektor D jest pierwszym wierszem macierzy wag krawędzi A.
Algorytm przebiega następująco:
  1. Dopóki zbiór Q nie jest pusty wykonuj:
  2. Pobierz ze zbioru Q wierzchołek v o najmniejszej wartości D[v] i usuń go ze zbioru.
  3. Dla każdego następnika i wierzchołka v dokonaj relaksacji ścieżki, tzn. sprwdź, czy D[i]>D[v]+A[v,i], tzn czy aktualne oszacowanie odległości do wierzchołka i jest większe od oszacowania odległości do wierzchołka v plus waga krawędzi (v,i).
    Jeżeli tak jest, to zaktualizuj oszacowanie D[i] przypisując mu prawą stronę nierówności (czyli mniejszą wartość).
Jak widać z powyższego pseudokodu, algorytm wybiera z kolejki Q "najlżejszy" wierzchołek, tzn. jest oparty o strategię zachłanną.
Wprawdzie metoda zachłanna nie zawsze daje wynik optymalny, jednak algorytm Dijkstry jest algorytmem dokładnym.
Oto przyładowy graf oraz jego macierz wag krawędzi (nieskończoność oznacza brak krawędzi):
ImageImage
Obliczenia przebiegają następująco: (Dla S=a)
(gwiazdka oznacza symbol nieskończoności, najlżejszy wierzchołek jest podkreślony, wierzchołki, dla których wyznaczono już najkrótsze ścieżki są pogrubione)
QD(a)D(b)D(c)D(d)D(e)
{b,c,d,e}010**5
{b,c,d}081475
{b,c}081375
{c}08975
{}08975

Istnieje kilka odmian implementacji Dijkstry; najprostsza używa tablicy do przechowywania wierzchołków ze zbiory Q. Inne wersje algorytmu używają kolejki priorytetowej lub kopca Fibonacciego.
Po znalezieniu najkrótszej odległości między wierzchołkami możemy znaleźć drogę łączącą te wierzchołki za pomocą algorytmu konstrukcji drogi.
Złożoność obliczeniowa: O(n2), przy implementacji bez użycia kopca. Z użyciem kopca można zejść do O(n log n).

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 26
Emil HotkowskiC/C++Kopiec Dijkstra , Vectory graf
.cpp
.cpp
***** / 6
mephistoJava
.java
.java
***** / 7
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 28 października 2012 15:30
Komentarze
photo
-4 # IlyaCk 2010-04-06 14:56
Dlaczego napisano \"Początkowo zbiór Q zawiera wszystkie wierzchołki a wektor D jest pierwszym wierszem macierzy wag krawędzi A\" ?

Nie zawsze pierszy, a ten, odleglosci od ktorego szukamy.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # ext 2012-02-09 23:31
W tabelce przechodząc przez b do c nie powinno być 11 zamiast 9 ?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # vaxquis 2012-12-11 14:48
oczywiście, że powinno... a->b = 10, b->c = 1, a->b->c = 11; krótszej drogi w tym grafie nie ma.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # powinno byc 9 2013-01-27 09:13
a->e->b->c =9 jak widac jest krotsza
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # vaxquis 2013-02-28 23:42
Nie w grafie {a,b,c}; krótsza droga jest tylko w grafie {a,b,c,d,e} - chyba o to chodziło ext-owi - bo to, że Djikstra dla pełnej wersji tego grafu relaksuje przez b trasę do c, i że najkrótsza trasa do c w grafie {a,b,c,d,e} ma długość 9, to jest oczywiste.

ext pisze 'W tabelce przechodząc przez b do c', więc ja się mogę tylko domyślać, co on miał na myśli. Nic w tabelce zamieszczonej na tej stronie nie przechodzi przez nic do niczego - w tabelce są tylko długości najkrótszych tras dla już przebadanej części grafu. Jeżeli on liczy trasy dla a, i przechodzi trasę z b do c, to wychodzi 11.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # DarkDewil 2012-04-11 15:10
akurat potrzebowalem schematu blokowego bo sam kod i ogolny algorytam kojarze ale nie bardzo wiem jak wykonac pare ostatnich polecen tzn jak je zapisac
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz