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 arrow \{1,2,...\} \) funkcją przypisująca krawędziom dodatnie liczby całkowite zwane wagami krawędzi. Krawędzie \( (u,w)\in E \) będziemy oznaczali przez \( u-w \).
Ciąg wierzchołków \( p= < v_0, v_1,\ldots , v_k > \) nazywamy ścieżką w \( G \) wtedy i tylko wtedy, gdy \( v_i - v_{i+1} \) jest krawędzią w \( E \), dla każdego \( i = 0, 1,\ldots,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.
Przez \( N(v) \) będziemy oznaczali zbiór sąsiadów wierzchołka \( v \) w grafie \( G \).
Problem (wag) najlżejszych ścieżek z jednym źródłem definiuje się następująco (uwaga: w literaturze przyjęło się też wagę ścieżki nazywać długością i dlatego często mówi się o problemie najkrótszych ścieżek).
Dane:
\( G=(V,E) \) – spójny, nieskierowany graf
\( w: Earrow \{1,2,\ldots\} \) – 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 \).
Na tym wykładzie zajmiemy się tylko wyznaczaniem wag najlżejszych ścieżek. Znalezienie sposobu wyznaczania takich ścieżek pozostawiamy jako ćwiczenie dla czytelnika. 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 większe 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 szczegó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ępujące proste spostrzeżenie:
Niech \( < v=v_0,v_1,\ldots,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)>\ldots > 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ć więcej 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.
Możemy teraz przystąpić do schematu algorytmu. Algorytm obliczania najlżejszych ścieżek będzie działał w \( n-1 \) fazach. W trakcie działania algorytmu \( L \) będzie zbiorem tych wierzchołków, dla których wagi najlżejszych scieżek prowadzące do \( s \) zostały już obliczone. Przez \( R \) będziemy oznaczali zbiór pozostałych wierzchołków. Podczas obliczeń z każdym wierzchołkiem \( v \) będziemy mieli związana nieujemną wagę \( w[v] \). Dla każdego wierzchołka \( v \in L \) waga \( w[v] \) będzie wagą najlżejszej scieżki łączacej \( v \) z \( s \), czyli \( w[v] = w^*(v) \). Dla każdego wierzchołka \( v \) z \( R \), \( w[v] \) będzie równe wadze najlżejszej ścieżki z \( v \) do \( s \), na której wszystkie wierzchołki poza \( v \) należą do \( L \). Może się zdarzyć, że taka ścieżka nie istnieje. Wówczas przyjmujemy, że \( w[v] \) jest równe \( \infty \) - umownej wartości większej od wszystkich wag występujących w obliczeniach. Jedna faza algorytmu będzie polegała na przeniesieniu do \( L \) wierzchołka z \( R \) o najmniejszej wadze \( w \), a następnie poprawieniu wag \( w \) dla wierzchołków, które pozostały w \( R \). Zauważmy, że wagi \( w \) mogą się zmienić tylko sąsiadom wierzchołka przeniesionego do \( L \), którzy pozostali w \( R \). Oto schemat algorytmu obliczania najlżejszych ścieżek. Nazwiemy go metodą Dijkstry.
Algorytm Metoda Dijkstry
//Inicjacja L := {s}; R := V- {s}; w[s] := 0; for each v in R do if v-s in E then w[v] := w(v-s) else w[v] := infty ; //właściwe obliczenia for i := 1 to n-1 do begin u := wierzchołek z R o minimalnej wadze w[u]; R := R - {u}; L := L + {u}; for each v in (N(u) cap R) do if w[u] + w(u-v) < w[v] then w[v] := w[u] + w(u-v); end; //dla każdego v in V, w[v] = w*(v)
Dlaczego powyższy opis obliczania wag najlżejszych ścieżek nazwaliśmy metodą Dijkstry, a nie algorytmem Dijkstry? Zauważmy, że żeby powyższą metodę móc zaimplementować na komputerze, a także dokonać analizy jej złożoności obliczeniowej, musimy doprecyzować wiele elementów schematu. Należą do nich
Dopiero ścisłe określenie tych elementów da nam pełną implementację metody, a tym samym algorytm, który będzie mógł być poddany analizie.
Zaczniemy od implementacji, w której wszystkie struktury danych są tablicami. Zanim to jednak zrobimy, zastanówmy się, w jaki sposób wygodnie zadać graf jako daną dla algorytmu. Zawyczaj przyjmuje się, że wierzchołki grafu utożsamiamy z liczbami naturalnymi \( 1,2,\ldots, n \), natomiast krawędzie opisujemy jako pary liczb odpowiadające końcom krawędzi. Gdy dodatkowo, tak jak w problemie najlżejszych ścieżek, z każdą krawędzią związana jest waga, to z każdą parą liczb opisującą końce krawędzi podajemy trzecią liczbę - wagę tej krawędzi. Tak więc graf możemy zadać w następujący sposób:
Zauważmy, że jeśli graf jest spójny, jego rozmiar wynosi \( O(m) \), gdzie \( n-1 < m \le \frac{n(n-1)}{2} \).
Taki sposób reprezentacji grafu nie jest wygodny w obliczeniach, ponieważ nie daje on prawie żadnej informacji o strukturze grafu. Dlatego w algorytmach grafowych przyjmuje się, że graf jest implementowany na jeden z dwóch sposobów.