Algorytm Dijkstry

25.11.2009 - Krzysztof Nowicki
TrudnośćTrudność

Popatrzmy na taką ośmiomiastową mapę (reprezentowaną jako ośmiowierzchołkowy graf ważony):

Miasta otrzymały numery, krawędzie odwzorowują drogi między miastami. Pytamy o najkrótszą z możliwych dróg z miasta $ A $ (nr 1) do miasta $ B $ (nr 7).

Tak jak wcześniej pokazywałem popatrzmy najpierw na wierzchołek (miasto) A i jego sąsiadów. Zaznaczę wierzchołek $ A $ na biało (wszystkie wierzchołki, dla których jestem pewien odpowiedzi będę zaznaczał na biało), wszystkich "sąsiadów" na czerwono, najbliższego z nich (który odgrywa ważną rolę w tym wszystkim) będę oznaczał na niebiesko. Dla $ A $ (miasto numer jeden) znamy odpowiedź na pewno, droga o długości 0 (dlatego obok miasta $ A $ pojawiło się białe 1->0, 1 to numer miasta, 0 to długość najkrótszej drogi jaką do tej pory udało się znaleźć, a biały kolor, ponieważ jestem już pewien, że odpowiedź się nie zmieni). Obok wierzchołka 2 i 3 pojawiły się podobne napisy oznaczające, że dla miasta 2 znamy jakąś drogę o długości 5, dla miasta 3 o długości 4. Kolor niebieski oznacza, że jest to najbliższe miasto z tych, dla których odpowiedzi jeszcze nie jesteśmy pewni, czerwony, że jest to jakaś propozycja długości drogi do miasta. Ponieważ miasto 3 jest bliżej niż 2, to miasto 3 jest niebieskie, a 2 czerwone.

Jednak jak już napisałem, jakby się tak przyjrzeć temu miastu nr 3, to faktycznie ta propozycja musi być ostateczną odpowiedzią (przez miasto 2 nie ma żadnej krótszej drogi do 3, bo sama droga do 2 jest dłuższa). Zatem mogę zaznaczyć na biało wierzchołek nr 3 i popatrzeć na jego sąsiadów i obliczyć ich odległość od $ A $.

Do wierzchołka 5 istnieje droga o długości 7 (z 1 do 3 o długości 4 i z 3 do 5 o długości 3, 4+3=7), do wierzchołka 4 droga o długości 8 oraz do wierzchołka 6 o długości 10. Drogi te wcześniej nie istniały, więc je wpisujemy jako dobre propozycje.

Istnieje też droga do wierzchołka 2 przez wierzchołek 3, ale ma ona długość 6, więc nie opłaca nam się jej sprawdzać, gdyż wiemy, że istnieje już nam znana lepsza droga o długości 5. Zatem wierzchołek 2 pozostawiamy bez zmiany odległości.

W czerwonym zbiorze sąsiadów jest teraz 2 z odległością 5(będę pisał 2->5), 5->7, 6->10, 4->8.  Niebieskim wierzchołkiem jest 2 (najbliższy A nie-biały wierzchołek), białe są 1->0 i 3->4.

Postępuję teraz tak samo, biorę najbliższy do A kolorowy wierzchołek (niebieski) wiem, że dla niego odpowiedź jest ok (policzyłem najkrótszą ścieżkę przez białe wierzchołki, a przez kolorowe byłaby dłuższa, gdyż dowolny inny kolorowy wierzchołek jest nie bliżej niż niebieski). Zatem koloruję go na biało i patrzę, czy istnieje jakaś korzystniejsza propozycja dla bezpośrednich sąsiadów 2. 1 i 3 mają już policzoną poprawną odpowiedź, nic lepszego już nie wymyślimy, do piątki znamy już lepszą drogę niż o długości 8, do szóstki znamy drogę o długości 10, czyli tak czy siak najkrótsza droga po białych do 6 ma długość 10.

2 staje się biały, 5 niebieski, zatem wiemy, że odpowiedź dla 5 jest już ok, sprawdzamy jego sąsiadów. Dla 2,3,6 nie możemy ułożyć żadnej krótszej drogi przez 5, za to do 7 możemy ułożyć. 7 staje się więc czerwonym "sąsiadem" $ A $ o odległości 14. Mamy więc propozycję długości drogi z $ A $ do $ B $. Jednak pewni jej poprawności będziemy dopiero w chwili, gdy 7 zrobi się niebieskie.

W tej chwili białe są 1->0 2->5 3->4 5->7, czerwone 6->10, 7->14, 4->8, zatem niebieski jest wierzchołek 4. Sprawdzamy jego sąsiadów i uaktualniamy co sie da na lepsze. Dla 6 i 3 nie ma nic lepszego, jadnak propozycja dla 7 jest o jeden krótsza niż dotychczasowa propozycja, wiec 7->14 zamieniamy na 7-> 13, dla ósemki mamy nową drogę, więc do czerwonych dochodzi też wierzchołek 8->12.

W kolejnych krokach nie dzieje się już nic istotnego, po prostu bierzemy niebieski wierzchołek i okazuje się, że nic lepszego już z niego nie wynika (akurat taki przykład)

Jednak dopiero gdy wierzchołek $ B $ będzie niebieski, mamy pewność, że odległość od $ A $ jest poprawnie policzona (raz już mieliśmy czerwoną odległość do B, którą poprawialiśmy, bo okazało się, że istnieje lepsza).

3.3
Twoja ocena: Brak Ocena: 3.3 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com