Algorytmy i struktury danych/Algorytmy grafowe - najlżejsze ścieżki

Ten wykład poświęcimy wprowadzeniu do algorytmów grafowych. W tym celu rozwiążemy jedno następujący problem ścieżkowy.

Najlżejsze ścieżki z jednym źródłem

W tym wykładzie pisząc graf będziemy mieli zawsze na uwadze graf spójny i nieskierowany. Tradycyjnie przez $n$ będziemy oznaczali liczbę wierzchołków w grafie, a przez $m$ liczbę jego krawędzi. Dla każdego grafu mamy zawsze $n-1\le m\le n(n-1)/2$.

Niech $G=(V,E)$ będzie grafem, a $w:E\to \{1,2,...\}$ funkcją przypisująca krawędziom dodatnie liczby całkowite zwane wagami krawędzi.

Ciąg wierzchołków $p=<v_0,v_1,\dots ,v_k>$ nazywamy ścieżką w G wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_i–v_{i+1}} jest krawędzią w $E$, dla każdego $i=1,2,\dots ,k-1$. Liczbę $k$ nazywamy długością ścieżki $p$.

Wagą ścieżki $p$ nazywamy sumę wag jej krawędzi i oznaczamy także przez $w(p)$. Przyjmujemy, że waga ścieżki o długości 0 wynosi 0.

Problem (wag) najlżejszych ścieżek z jednym źródłem definiuje się nastepująco.

Dane:
  $G=(V,E)$ – spójny, nieskierowany graf
  $w:E\to \{1,2,\dots \}$ – funkcja przypisująca krawędziom   dodatnie liczby całkowite
  $s$ – wyróżniony wierzchołek w G, zwany źródłem
Wynik:
  dla każdego wierzchołka $v$ waga $w*(v)$ najlżejszej ścieżki łączącej v z s.

W tym wykładzie zajmiemy się tylko wyznaczaniem wag najlżejszych ścieżek. Znalezienie sposobu wyznaczania takich ścieżek pozstawimy jako ćwiczenie dla czytelników. Problem najlżejszych scieżek jest problemem bardzo naturalnym. Jeśli mapę drogową potraktować jako graf, w którym wagi to długości odcinków drogowych na mapie, a źródło jest wyróżnionym miastem na mapie (na przykład stolicą państwa), to rozwiązanie problemu najlżejszych ścieżek da nam długości najkrótszych dróg od miasta-źródła do pozostałych miast na mapie.

Znaczenie problemu najlżejszych ścieżek jest dużo ważniejsze niż by to wynikało z jego zastosowań. Poszukując wydajnego algorytmu dla rozwiązania tego problemu postaramy się przedstawić cały proces projektowania, a następnie implementowania algorytmu ze szczegtólnym uwzględnieniem doboru odpowiednich struktur danych w celu osiągnięcia lepszej wydajności implementacji.

Nasze rozważania rozpoczniemy od schematu algorytmu poszukiwania najlżejszych ścieżek, a następnie zajmiemy się implementacją poszczególnych elementów tego schematu. Rozwiązanie, które zaproponujemy pochodzi od wybitnego holenderskiego informatyka Edgara Dijkstry.

Zastanówmy się w jaki sposób obliczać wagi najlżejszych ścieżek. Pomoże nam w tym następujace proste spostrzeżenie:

Niech $<v=v_0,v_1,\dots ,v_k=s>$ będzie najlżejszą ścieżką z wierzchołka $v$, do źródła $s$. Wówczas $w^{*}(v)>w^{*}(v_1)>\dots >w^{*}(v_k)=0$.

Spostrzeżenie to mówi, że gdybyśmy obliczali wagi najlżejszych ścieżek od najlżejszej do najcięższej, to dla każdego wierzchołka $v$ różnego od źródła, sąsiad $v$ na najlżejszej ścieżce z $v$ do $s$ miałby swoją wagę już obliczoną i tym sąsiadem byłby wierzchołek (może być wiecej niż jeden wybór, dla którego waga najlżejszej ścieżki do $s$ powiększona o wagę krawędzi łączącej go z $v$ jest najmniejsza.