Algorytm Dijkstry

25.11.2009 - Krzysztof Nowicki
TrudnośćTrudność

Zagadnienie znajdowania najkrótszej ścieżki jest dość często spotykane. Czasem widać je wprost, czasem jest jednak tylko małą częścią trudniejszego problemu, jednak niezbędną, by go rozwiązać. Dlatego dogłębne poznanie tego zagadnienia (oraz sposobu jego rozwiązania) jest bardzo ważne dla wszystkich, którzy chcieliby umieć rozwiązywać owe łatwe zadania, gdzie widać od razu, że wystarczy znaleźć najkrótszą drogę, a jeszcze ważniejsze dla tych, którzy chcieliby rozwiązywać te trochę trudniejsze zadania.

Problem

Rozważmy dostawcę, takiego normalnego człowieka, który ma samochód i musi przejechać z miasta $ A $ do miasta $ B $. Dysponuje on mapą, na której zaznaczone są wszystkie miejscowości w regionie, oraz zaznaczone jest, z której miejscowości do której można dojechać drogą nieprzechodzącą przez inną miejscowość (drogi krzyżują się tylko w miastach, między nimi omijają się tunelami czy estakadami). Kierowca jest zmęczony i chce jak najszybciej wrócić do domu, pytamy więc zatem jaka jest najkrótsza droga z miasta $ A $ do miasta $ B $.

Dlaczego nie BFS?

Gdyby wszystkie bezpośrednie drogi pomiędzy miastami miały tą samą długość, to całą tą mapę można by przedstawić jako zwykły graf o krawędziach jednostkowych, i znaleźć tą najkrótszą ścieżkę algorytmem BFS. Co jeśli jednak drogi te nie są tej samej długości?
Można by podzielić te drogi na pewne odcinki, tak, żeby każda droga składała się z kilku odcinków, wszystkich tej samej długości. Wtedy na dłuższych drogach można by ustawić kilka "sztucznych miast" tak, żeby każde dwa miasta łączyły się drogą o tej samej długości i użyć BFS-a. Co jeśli jednak drogi są długie i takich miast trzeba by wstawić bardzo dużo? Algorytm BFS nie jest jednak zbyt skutecznym sposobem rozwiązywania tego problemu.

Algorytm Dijkstry

Rozważmy tą mapę jako graf ważony, tzn. wierzchołkom przypiszmy miasta, krawędziom pomiędzy wierzchołkami (miastami) wagi równe długościom dróg pomiędzy nimi. BFS jest bezużyteczny (może znaleźć drogę przez najmniejszą ilość miast), ale można skorzystać z
algorytmu Dijkstry. Pozwala on właśnie na znalezienie odległości wszystkich miast na takiej mapie od miasta $ A $ (warunkiem jest to, by wagi krawędzi były nieujemne). W szczególności pozwala nam również obliczyć odległość do miasta $ B $.

Wyobraźmy sobie, ze jesteśmy w mieście $ A $. To co w tej chwili wiemy, to tyle, że nie musimy się nigdzie ruszać, aby dojechać do miasta $ A $, zatem można powiedzieć, że znajdujemy się w odległości 0 od miasta $ A $. Poza tym z mapy możemy odczytać, w jakiej odległości znajdują się miasta połączone bezpośrednią drogą z $ A $. Popatrzmy teraz na miasto, które jest najbliżej. Nazwijmy je $ X $. Patrząc na nie tak dokładniej można dojść do wniosku, że istotnie długość drogi z $ A $ do $ X $ jest odległością miasta $ X $ od miasta $ A $.

Dowód

Gdyby tak nie było, to musiałoby istnieć taka droga poprzez inne miasta, że byłaby krótsza od bezpośredniej drogi z $ A $ do $ X $ (może być równa, ale to nie zmieniłoby faktu, że ta, którą wybraliśmy nadal jest jedną z najkrótszych). Ponieważ drogi mają nieujemne długości, to musiałoby istnieć jakieś miasto $ C $ sąsiadujące z $ X $, przez które ta droga by szła. Ponieważ sumarycznie droga ta ma być krótsza niż bezpośrednia droga z $ A $ do $ X $, to żadna jej część składowa nie może być dłuższa niż długość bezpośredniej drogi z $ A $ do $ X $, zatem długość drogi z $ A $ do $ C $ musiałaby być mniejsza niż z $ A $ do $ X $. To jest sprzeczne z tym, że miasto $ X $ wybraliśmy jako to, które jest najbliżej od miasta $ A $.

Rozumowanie takie można oczywiście rozszerzyć... mamy teraz 2 miasta, wiemy, że z miasta $ A $ do $ X $ najkrótsza ścieżka ma jakąś długość. Nazwijmy ją jakoś (tą długość), niech będzie $ a $. Zatem wiadomo, że do każdego z sąsiadów $ Y $(tak sobie nazwijmy sąsiada $ X $)miasta $ X $ możemy dojechać z miasta $ A $ jakąś drogą złożoną z dwóch fragmentów: droga z miasta $ A $ do $ X $ oraz z $ X $ do $ Y $. Można zatem potraktować $ Y $ jako sąsiada $ A $ połączonego drogą o długości ($ a $ + długość drogi z $ X $ do $ Y $). Popatrzmy teraz na takich "sąsiadów" miasta $ A $.
Weźmy teraz najbliższego z nich (poza miastem $ X $, bo dla niego znamy już ostateczną odpowiedź) i wybierzmy najbliższego z nich. Nazwijmy to miasto $ Z $. Jak się tak głębiej zastanowić nad miastem $ Z $, to znów możemy powiedzieć, że odległość tego miasta od $ A $ jest długością drogi z $ A $ do $ Z $ (tym razem już niekoniecznie bezpośredniej, może być to równie dobrze droga przez $ X $).

Kłopotliwe miasto

Z jednym małym wyjątkiem... co jeśli w ten sposób wybraliśmy miasto $ A $? Otóż aby temu zapobiec musimy przestać traktować miasto $ A $ (dla którego znamy już odpowiedź) jako sąsiada miasta $ X $, gdyż droga z miasta $ A $ do miasta $ A $ przez jakieś inne miasto na pewno nie może mieć długości mniejszej niż 0 (więc w ten sposób nie uzyskamy lepszej odpowiedzi). 

Skoro już przebrnęliśmy przez ten wyjątek jesteśmy pewni że odległość miasta $ Z $ od $ A $ to długość ścieżki z $ Z $ do $ A $. Można to udowodnić w analogiczny sposób jak dla miasta $ X $ (zakładając że istnieje taka ścieżka i dochodząc do sprzeczności z tym, że $ Z $ jest w tej chwili najbliższym interesującym nas "sąsiadem" miasta $ A $).

Rozumowanie to jest jak na razie zadowalające i zapewne można je nadal rozszerzać.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com