Problem znajdowania najkrótszej drogi

Wyobraźmy sobie pewną mapę. Na mapie zaznaczone są drogi między poszczególnymi miastami oraz długości tych dróg. Wybierając z tej mapy dowolne dwa miasta A i B chcemy zaplanować najkrótszą trasę z miasta A do miasta B.

Jak rozwiązać ten problem używając grafów ?
Stwórzmy graf, którego wierzchołki odpowiadają miastom znajdującym sie na danej mapie. Wierzchołki łączymy krawędzią jeśli istnieje bezpośrednia (nie przebiegająca przez żadne inne miasto zaznaczone na tej mapie) droga łącząca odpowiadające im miasta. Krawędziom nadajemy wagi równe długości danej drogi. Oczywiście długość drogi możemy zastąpić przez czas trwania podróży lub jej koszt. Znalezienie najkrótszej drogi z miasta A do miasta B oznacza znalezienie pomiędzy odpowiadającymi im wierzchołkami drogi o możliwie najmniejszej sumie wag krawędzi.

Kiedy rozwiązanie tego problemu istnieje ?
Jesteśmy w stanie znaleźć najkrótszą drogę, jeśli droga między danymi miastami (wierzchołkami w grafie) w ogóle istnieje. Aby można było znaleźć najkrótsze drogi między dowolną parą miast utworzony dla danej mapy graf musi być spójny.

Algorytm rozwiązujący ten problem.
Najbardziej znanym algorytmem rozwiązującym ten problem jest algorytm Dijkstry.

Opis algorytmu Dijkstry
Algorytm Dijks znajduje najkrótszą drogę z wierzchołka $s$ (zwanego źródłem) do wierzchołka $t$ (zwanego ujściem) w grafie, w którym wszystkim krawędziom nadano nieujemne wagi. Polega na przypisaniu wierzchołkom pewnych wartości liczbowych. Taką liczbę nazwijmy cechą wierzchołka. Cechę wierzchołka $v$ nazwiemy stałą (gdy jest równa długości najkrótszej drogi z $s$ do $v$) albo, w przeciwnym przypadku, tymczasową. Na początku wszystkie wierzchołki, oprócz $s$, otrzymują tymczasowe cechy $\infty$. źródło $s$ otrzymuje cechę stałą równą $0$. Następnie wszystkie wierzchołki połączone krawędzią z wierzchołkiem $s$ otrzymują cechy tymczasowe równe odległości od $s$. Potem wybierany jest spośród nich wierzchołek o najmniejszej cesze tymczasowej. Oznaczmy go $v$. Cechę tego wierzchołka zamieniamy na stałą oraz przeglądamy wszystkie wierzchołki połączone z $v$. Jeśli droga z $s$ do któregoś z nich, przechodząca przez $v$ ma mniejszą długość od tymczasowej cechy tego wierzchołka, to zmniejszamy tą cechę. Ponownie znajdujemy wierzchołek o najmniejszej cesze tymczasowej i zamieniamy cechę tego wierzchołka na stałą. Kontynuujemy to postępowanie aż do momentu zamiany cechy wierzchołka $t$ na stałą (czyli obliczenia długości najkrótszej drogi z $s$ do $t$).

Zastosowania.
Algorytmy znajdujące najkrótszą drogę w grafie są wykorzystywane do wyznaczania najlepszej trasy pomiędzy dwoma miastami na 'komputerowych' mapach. Mapy takie przydatne są w pracy np. firm transportowych.

[ Początek strony ] [ MiNIWykłady ]

---

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej