Implementacja algorytmu Dijkstry w języku Python

W tej sekcji zapoznamy się z implementacją algorytmu Dijkstry w języku Python.

Specyfikacja problemu:

Dane:

• listaSasiedztwa – lista sąsiedztwalista sąsiedztwalista sąsiedztwa spójnegograf spójnyspójnego grafu nieskierowanegograf nieskierowanynieskierowanego o dodatnich wagachwaga krawędziwagach

• s – indeks wierzchołkawierzchołekwierzchołka początkowego grafu

• V – liczba naturalna dodatnia; liczba wierzchołków grafu

Wynik:

• tablica przechowująca najkrótsze ścieżkinajkrótsza ścieżkanajkrótsze ścieżki od wierzchołka s do pozostałych wierzchołków oraz tablica przechowująca poprzedniki kolejnych wierzchołków

Działanie programu przetestujemy dla następującego grafu:

R1KqoeFniUL5u

Ilustracja przedstawia graf z węzłami oznaczonymi literami oraz łączącymi je krawędziami oznaczone cyframi.
A, 4, C. A, 1, B. B, 1, E. B, 6, G. B, 3, F. C, 2, D. C, 2, G. D, 12, F.

Przyjmijmy założenie, że wierzchołkiem początkowym jest wierzchołek E (o indeksie równym 4).

Oto lista sąsiedztwa tego grafu:

listaSasiedztwa = [
	[[[1, 1], [2, 4]]],                     # dla wierzcholka 0 (A)
	[[[0, 1], [4, 1]], [[5, 3], [6, 6]]],   # dla wierzcholka 1 (B)
	[[[0, 4], [3, 5]], [[6, 2]]],           # dla wierzcholka 2 (C)
	[[[2, 5]], [[5, 12]]],                  # dla wierzcholka 3 (D)
	[[[1, 1]]],                             # dla wierzcholka 4 (E)
	[[[1, 3]], [[3, 12]]],                  # dla wierzcholka 5 (F)
	[[[1, 6]], [[2, 2]]]                    # dla wierzcholka 6 (G)
]

W naszym przypadku ważona lista sąsiedztwa (czyli lista sąsiedztwa grafu z wagami [ważonegograf ważony[ważonego]) jest tablicą trójwymiarową.

Zapiszemy w języku Python program, który dla danego grafu reprezentowanego przez listę sąsiedztwa wyświetlić dwie tablice: tablicę najkrótszych ścieżek do danych wierzchołków z wierzchołka początkowego oraz tablicę ich poprzedników.

Zaczniemy od utworzenia dwóch zmiennych oraz przypisania im wartości:

• V – liczba wierzchołków w grafie;

• nieskonczonosc – zmienna służąca do inicjowania odległości w algorytmie Dijkstry; przypiszemy jej odpowiednio dużą wartość (minimalna przypisana wartość powinna być większa od iloczynu liczby wierzchołków oraz największej z wag krawędzikrawędźkrawędzi).

V = 7
nieskonczonosc = 1000

W kolejnym kroku zapisujemy nagłówek funkcji Dijkstra. Funkcja przyjmie dwa parametry:

• tablicę sąsiedztwa listaSasiedztwa;

• indeks wierzchołka początkowego s, czyli liczbę naturalną.

def Dijkstra(listaSasiedztwa, s):

W programie konieczne jest zdefiniowanie tablic, z których każda pełni istotną funkcję:

• d – tablica długości ścieżekdługość ścieżki (koszt dojścia)długości ścieżek (liczb naturalnych); element na pozycji i oznacza aktualną długość ścieżki prowadzącej z wierzchołka początkowego do wierzchołka i;

• p – tablica poprzedników najkrótszych ścieżek (liczb naturalnych); element na pozycji i oznacza indeks poprzedniego wierzchołka na najkrótszej ścieżce do wierzchołka i; za brak poprzednika uznajemy wartość -1;

• S – tablica wierzchołków znajdujących się w zbiorze S (wartości logicznych); jeśli element na pozycji i jest równy True, oznacza to, że wierzchołek i znajduje się w zbiorze S; domyślnie wszystkie elementy są równe False.

Wypełniamy tablice odpowiednimi wartościami. Wszystkie tablice będą składać się z V elementów (czyli liczby wierzchołków).

• elementom tablicy d przypisujemy wartość nieskonczonosc;

• elementom tablicy p przypisujemy wartość -1;

• elementom tablicy S przypisujemy wartość False.

Elementowi tablicy d o indeksie s przypisujemy wartość 0, ponieważ odległość wierzchołka początkowego do siebie samego wynosi 0.

Deklarujemy również zmienną odwiedzony – będzie ona licznikiem wierzchołków, które zostały odwiedzone. Gdy jej wartość będzie równa wartości przechowywanej przez zmienną V (całkowitą liczbę wierzchołków w grafie), będzie to oznaczać, że wszystkie wierzchołki zostały przetworzone i algorytm może zakończyć swoje działanie. Przypisujemy jej wartość 0.

V = 7
nieskonczonosc = 1000

def Dijkstra(listaSasiedztwa, s):
    d = [nieskonczonosc] * V
    p = [-1] * V
    S = [False] * V
    
    d[s] = 0
    odwiedzony = 0

Zapisujemy pętlę while, która będzie wykonywać się tak długo, aż znajdziemy najkrótsze ścieżki i poprzedników dla wszystkich wierzchołków grafu.

W pętli deklarujemy zmienną u, którą inicjalizujemy wartością -1. Zmienna ta posłuży  jako flaga i będzie wskazywać, czy udało się znaleźć odpowiedni wierzchołek – taki, który nie został jeszcze odwiedzony, a jego odległość od sprawdzanego wierzchołka jest najmniejsza.

Zapisujemy pętlę for. Iterujemy przez elementy tablicy S, szukając pierwszego nieodwiedzonego wierzchołka grafu.

W pętli for zapisujemy instrukcję warunkową. By instrukcja warunkowa zwróciła wartość True, muszą zostać spełnione dwa warunki:

• wierzchołek nie został jeszcze odwiedzony (not S[i], gdzie S to tablica wartości logicznych wskazująca, czy wierzchołek został odwiedzony);

• u wciąż jest równe -1 (co oznacza, że jest to pierwszy znaleziony nieodwiedzony wierzchołek) lub tymczasowa odległość d[i] do tego wierzchołka jest mniejsza niż tymczasowa odległość d[u] do wierzchołka, który znaleźliśmy wcześniej.

Jeśli oba warunki są spełnione, przypisujemy bieżący indeks i do u. Po zakończeniu tej pętli zmienna u będzie przechowywać indeks nieodwiedzonego wierzchołka o najmniejszej tymczasowej odległości lub pozostanie -1, jeśli wszystkie wierzchołki zostały już odwiedzone.

Po wybraniu wierzchołka u z najkrótszą odległością oznaczamy go jako odwiedzony. Następnie zwiększamy licznik odwiedzonych wierzchołków.

V = 7
nieskonczonosc = 1000

def Dijkstra(listaSasiedztwa, s):
    d = [nieskonczonosc] * V
    p = [-1] * V
    S = [False] * V
    
    d[s] = 0
    odwiedzony = 0
    
    while odwiedzony < V:
        u = -1
        for i in range(V):
            if not S[i] and (u == -1 or d[i] < d[u]):
                u = i
        if u == -1:
            break
        S[u] = True
        odwiedzony += 1

Zapisujemy pętlę for, która będzie iterować po wszystkich listach sąsiadów wierzchołka u. W tej pętli zapisujemy zagnieżdżoną pętlę for, która z kolei będzie iterować po tablicach przechowujących indeks sąsiada wierzchołka u (czyli v) oraz wagę łączących te dwa wierzchołki krawędzi (waga).

W pętli for zapisujemy instrukcję warunkową. By instrukcja warunkowa zwróciła wartość True, muszą zostać spełnione dwa warunki:

• wierzchołek nie został jeszcze odwiedzony (!S[i], gdzie S to tablica wartości logicznych wskazująca, czy wierzchołek został odwiedzony);

• tymczasowa odległość d[i] do tego wierzchołka jest mniejsza niż tymczasowa odległość d[u] do wierzchołka, który znaleźliśmy wcześniej.

Jeżeli oba te warunki są spełnione, oznacza to, że znaleźliśmy krótszą ścieżkę do wierzchołka v. Aktualizujemy więc nową odległość do wierzchołka v, która jest sumą odległości do u oraz wagi krawędzi łączącej wierzchołki u i v, a także wartość poprzednika wierzchołka v na ścieżce, którym jest wierzchołek u.

V = 7
nieskonczonosc = 1000

def Dijkstra(listaSasiedztwa, s):
    d = [nieskonczonosc] * V  
    p = [-1] * V            
    S = [False] * V          
    
    d[s] = 0  
    odwiedzony = 0  
    
    while odwiedzony < V:
        u = -1
        for i in range(V):
            if not S[i] and (u == -1 or d[i] < d[u]):
                u = i
        if u == -1:
            break
        S[u] = True
        odwiedzony += 1
        
        for i in range(len(listaSasiedztwa[u])):
            for v, waga in listaSasiedztwa[u][i]:
                if not S[v] and d[u] + waga < d[v]:
                    d[v] = d[u] + waga
                    p[v] = u

Po wykonaniu tego fragmentu kodu dla każdego wierzchołka sąsiadującego z u mamy pewność, że odległość d[v] do niego jest najkrótszą odległością, a p[v] przechowuje wierzchołek, przez który prowadzi ta najkrótsza ścieżka.

Dodajemy instrukcje odpowiedzialne za wywołanie funkcji i odpowiednie wyświetlenie wyników.

Oto kompletny kod programu:

V = 7
nieskonczonosc = 1000

def Dijkstra(listaSasiedztwa, s):
    d = [nieskonczonosc] * V  
    p = [-1] * V            
    S = [False] * V          
    
    d[s] = 0  
    odwiedzony = 0  
    
    while odwiedzony < V:
        u = -1
        for i in range(V):
            if not S[i] and (u == -1 or d[i] < d[u]):
                u = i
        if u == -1:
            break
        S[u] = True
        odwiedzony += 1
        
        for i in range(len(listaSasiedztwa[u])):
            for v, waga in listaSasiedztwa[u][i]:
                if not S[v] and d[u] + waga < d[v]:
                    d[v] = d[u] + waga
                    p[v] = u
    
    print("d[] =", d)
    print ("p[] =", p)

listaSasiedztwa = [
    [[[1, 1], [2, 4]]],                    # dla wierzcholka 0 (A)
    [[[0, 1], [4, 1]], [[5, 3], [6, 6]]],  # dla wierzcholka 1 (B)
    [[[0, 4], [3, 5]], [[6, 2]]],          # dla wierzcholka 2 (C)
    [[[2, 5]], [[5, 12]]],                 # dla wierzcholka 3 (D)
    [[[1, 1]]],                            # dla wierzcholka 4 (E)
    [[[1, 3]], [[3, 12]]],                 # dla wierzcholka 5 (F)
    [[[1, 6]], [[2, 2]]]                   # dla wierzcholka 6 (G)
]

Dijkstra(listaSasiedztwa, 4)

Wynik działania programu dla analizowanego grafu:

d[] = [ 2 1 6 11 0 4 7 ]
p[] = [ 1 4 0 2 -1 1 1 ]

Słownik