Algorytm Dijkstry - Polski Serwis Naukowy

Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.

Działanie

Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków. Łatwo zmodyfikować go tak, aby szukał wyłącznie (najkrótszej) ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego, bądź transponując tablicę incydencji grafu.

Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.
Edsger Wybe Dijkstra (ur. 11 maja 1930 w Rotterdamie, zm. 6 sierpnia 2002 w Neunen) - holenderski naukowiec, pionier informatyki. Twórca terminów bit i bajt.

Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym wierzchołkiem a wszystkimi pozostałymi, przy okazji wyliczając również koszt przejścia każdej z tych ścieżek.

Algorytm Dijkstry jest przykładem algorytmu zachłannego.

Algorytm

Przez $s$ oznaczamy wierzchołek źródłowy, $w(i, j)$ to waga krawędzi $(i, j)$ w grafie.

Stwórz tablicę $d$ odległości od źródła dla wszystkich wierzchołków grafu. Na początku $d[s]=0$ , zaś $d[v]=$ nieskończoność dla wszystkich pozostałych wierzchołków.

Utwórz kolejkę priorytetową $Q$ wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego $s$ .

Dopóki kolejka nie jest pusta:

Usuń z kolejki wierzchołek $u$ o najniższym priorytecie (wierzchołek najbliższy źródła, który nie został jeszcze rozważony)

Dla każdego sąsiada $v$ wierzchołka $u$ dokonaj relaksacji poprzez $u$ : jeśli $d[u] + w(u, v) < d[v]$ (poprzez $u$ da się dojść do $v$ szybciej niż dotychczasową ścieżką), to $d[v] := d[u] + w(u, v)$ .

Na końcu tablica $d$ zawiera najkrótsze odległości do wszystkich wierzchołków.

Trasowanie (ang. routing, pol. ruting, routowanie) – w informatyce wyznaczanie trasy i wysłanie nią pakietu danych w sieci komputerowej. Urządzenie węzłowe, w którym kształtowany jest ruch sieciowy, nazywane jest routerem, może to być np. komputer stacjonarny lub dedykowane urządzenie (również nazywane routerem).
Holandia (nid. Nederland) – europejska część Królestwa Niderlandów (nid. Koninkrijk der Nederlanden), tworzonego także przez Arubę i Antyle Holenderskie. Holandia jest członkiem Unii Europejskiej (UE), Unii Zachodnioeuropejskiej (UZE), ONZ oraz NATO. Holandia jest monarchią konstytucyjną położoną w zachodniej części Europy nad Morzem Północnym, które oblewa ją od północy i zachodu. Graniczy na południu z Belgią oraz na wschodzie z Niemcami. Obecne granice wytyczono w roku 1839.

Dodatkowo możemy w tablicy poprzednik przechowywać dla każdego wierzchołka numer jego bezpośredniego poprzednika na najkrótszej ścieżce, co pozwoli na odtworzenie pełnej ścieżki od źródła do każdego wierzchołka – przy każdej relaksacji w ostatnim punkcie $u$ staje się poprzednikiem $v$ .

Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree ) jest to drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.
Kopiec (ang. heap, tłumaczone też jako stóg lub sterta) – w informatyce struktura danych oparta na drzewie, w której wartości potomków węzła są w stałej relacji z wartością rodzica (na przykład wartość rodzica jest zawsze większa lub równa wartości potomka).

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)