Implementacja - I_R_W14_M38_Java Podejście zachłanne. Najkrótsza droga w grafie

R1GJG6M5BA9OA

Implementacja algorytmu Dijkstry w języku Java

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

Specyfikacja problemu:

Dane:

listaSasiedztwa – lista sąsiedztwa spójnego grafu nieskierowanego o dodatnich wagach
s – indeks wierzchołka początkowego grafu
V – liczba naturalna dodatnia; liczba wierzchołków grafu

Wynik:

tablica przechowująca najkró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. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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

Oto lista sąsiedztwa tego grafu:

Linia 1. static int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy listaSasiedztwa znak równości otwórz nawias klamrowy. Linia 2. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 4 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 0 otwórz nawias okrągły A zamknij nawias okrągły. Linia 3. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 4 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 6 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 1 otwórz nawias okrągły B zamknij nawias okrągły. Linia 4. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 4 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 2 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 2 otwórz nawias okrągły C zamknij nawias okrągły. Linia 5. otwórz nawias klamrowy otwórz nawias klamrowy 2 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 12 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 3 otwórz nawias okrągły D zamknij nawias okrągły. Linia 6. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 4 otwórz nawias okrągły E zamknij nawias okrągły. Linia 7. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 12 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 5 otwórz nawias okrągły F zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 6 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 2 zamknij nawias klamrowy zamknij nawias klamrowy prawy ukośnik prawy ukośnik dla wierzcholka 6 otwórz nawias okrągły G zamknij nawias okrągły. Linia 9. zamknij nawias klamrowy średnik.

static int[][][] 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)
};

Już wiesz

Przypomnijmy, w jaki sposób odczytywać listę sąsiedztwa.

Dla wierzchołka A mamy dwie tablice dwuelementowe. Pierwsza to {1,1}; jej pierwszy element to indeks sąsiedniego wierzchołka, a drugi – waga krawędzi. Odczytujemy to w ten sposób, że wierzchołek A jest połączony z wierzchołkiem B krawędzią o wadze 1. Analogicznie odczytujemy kolejną parę: wierzchołek A jest połączony z wierzchołkiem C krawędzią o wadze 4.

Zapis {-1,-1} oznacza, że dany wierzchołek nie jest połączony krawędzią z wierzchołkiem o danym indeksie. W przypadku wierzchołka A widzimy, że nie ma on połączeń z kolejnymi wierzchołkami (poza B oraz C), ponieważ odpowiednie podtablice przechowują dwie wartości -1.

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

Pierwszy wymiar określa liczbę wierzchołków grafu, drugi określa maksymalną liczbę sąsiadów, trzeci zaś składa się z dwóch elementów – jeden służy do przechowywania indeksu wierzchołka‑sąsiada, a drugi do przechowywania wagi krawędzi prowadzącej do tego sąsiada.

Zapiszemy w języku Java 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.

Zaczynamy od importu niezbędnej biblioteki import java.util.Arrays;.

W kolejnym kroku definiujemy klasę publiczną GrafDijkstra oraz tworzymy cztery zmienne:

V – zmienna statyczna definiująca liczbę wierzchołków w grafie;
maksymalnieSasiadow – zmienna statyczna, której przypisujemy różnicę wartości stałej V oraz liczby 1; wynika to z tego, że dany wierzchołek może mieć za sąsiadów maksymalnie wszystkie pozostałe wierzchołki;
NIESKONCZONOSC – zmienna statyczna 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ędzi);
listaSasiedztwa– tablica trójwymiarowa reprezentująca listę sąsiedztwa grafu.

import java.util.Arrays;

public class GrafDijkstra {
    static int V = 7;
	static int maksymalnieSasiadow = V - 1;    
    static int NIESKONCZONOSC = 10000;
    static int[][][] 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)
    };

Ważne!

Alternatywą dla wykorzystania zmiennej NIESKONCZONOSC jest użycie stałej Integer.MAX_VALUE.

W kolejnym kroku definiujemy statyczną metodę Dijkstra, która przyjmie dwa parametry:

tablicę sąsiedztwa listaSasiedztwa,
indeks wierzchołka początkowego s, czyli liczbę naturalną.

static void Dijkstra(int[][][] listaSasiedztwa, int s) {

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

d[V] – tablica długości ścieżek (liczb naturalnych); element na pozycji i oznacza aktualną długość ścieżki od wierzchołka początkowego do wierzchołka i;
p[V] – 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[V] – 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.

import java.util.Arrays;

public class GrafDijkstra {
    static int V = 7;
	static int maksymalnieSasiadow = V - 1;    
    static int NIESKONCZONOSC = 10000;
    static int[][][] 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)
    };

    static void Dijkstra(int[][][] listaSasiedztwa, int s) {
        int[] d = new int[V];
        int[] p = new int[V];
        boolean[] S = new boolean[V];  
    };        
};

Zapisujemy pętlę for. Będziemy iterować po elementach wcześniej utworzonych tablic. Dla każdego v-tego elementu tablic wykonamy następujące operacje:

v-temu elementowi tablicy d przypiszemy wartość NIESKONCZONOSC;
v-temu elementowi tablicy p przypiszemy wartość równą -1.

Po wyjściu z pętli 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), znaczy to, że wszystkie wierzchołki zostały przetworzone i algorytm może zakończyć swoje działanie.

import java.util.Arrays;

public class GrafDijkstra {
    static int V = 7;
	static int maksymalnieSasiadow = V - 1;    
    static int NIESKONCZONOSC = 10000;
    static int[][][] 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)
    };

    static void Dijkstra(int[][][] listaSasiedztwa, int s) {
        int[] d = new int[V];
        int[] p = new int[V];
        boolean[] S = new boolean[V];
        for (int i = 0; i < V; i++) {
            d[i] = NIESKONCZONOSC;
            p[i] = -1;
        }
        d[s] = 0;
        int 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.

W pętli while zapisujemy pętlę for. Iterujemy przez wierzchołki grafu.

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

sprawdzany wierzchołek nie został jeszcze odwiedzony (!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 równa -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.

import java.util.Arrays;

public class GrafDijkstra {
    static int V = 7;
	static int maksymalnieSasiadow = V - 1;    
    static int NIESKONCZONOSC = 10000;
    static int[][][] 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)
    };

    static void Dijkstra(int[][][] listaSasiedztwa, int s) {
        int[] d = new int[V];
        int[] p = new int[V];
        boolean[] S = new boolean[V];
        for (int i = 0; i < V; i++) {
            d[i] = NIESKONCZONOSC;
            p[i] = -1;
        }
        d[s] = 0;
        int odwiedzony = 0;

        while (odwiedzony < V) {
            int u = -1;
            for (int i = 0; i < V; i++) {
                if (!S[i] && (u == -1 || d[i] < d[u])) {
                    u = i;
                }
            }

            S[u] = true;
            odwiedzony++;
		}
	};
};

Zapisujemy kolejną pętlę for, która będzie iterować po sąsiadach u-tego wierzchołka. Pętla wykonuje się dla każdego wierzchołka u, który został wybrany jako wierzchołek o obecnie najkrótszej odległości od wierzchołka początkowego, ale nie został jeszcze odwiedzony. Pętla ta ma dwa warunki:

i < maksymalnieSasiadow – warunek, którym sprawdzamy, czy nie przekraczamy maksymalnej liczby możliwych sąsiadów (w przypadku grafu pełnego każdy wierzchołek miałby V - 1 sąsiadów);
i < listaSasiedztwa[u].length – warunek, którym sprawdzamy, czy osiągnęliśmy koniec listy sąsiadów dla wierzchołka u.

Dla każdego sąsiada wierzchołka u sprawdzamy, czy znaleźliśmy krótszą ścieżkę i możemy zaktualizować znaną odległość od wierzchołka początkowego (s) do tego sąsiada (v).

Pobieramy dane z tablicy listaSasiedztwa.

Przypisujemy zmiennej v (indeksowi wierzchołka sąsiadującego z wierzchołkiem u) wartość listaSasiedztwa[u][i][0], a zmiennej waga (wadze krawędzi między wierzchołkiem u oraz jego sąsiadem‑wierzchołkiem v) – wartość listaSasiedztwa[u][i][1].

Dodajemy warunek przerwania pętli. Jeśli w trakcie iteracji natrafimy na wartość -1 dla v, to znaczy, że osiągnęliśmy koniec listy sąsiadów dla wierzchołka u, zatem nie ma potrzeby dalszego iterowania.

Następnie zapisujemy instrukcję warunkową, w której sprawdzamy, czy obecna odległość do wierzchołka v (czyli wartość przechowywana w d[v]) jest większa niż suma odległości do wierzchołka u (d[u]) i wagi krawędzi między wierzchołkami u oraz v (czyli waga). Innymi słowy, czy przejście przez u do v jest krótsze niż bezpośrednie połączenie do v (jeśli takie istnieje).

Jeśli tak, oznacza to, że znaleźliśmy krótszą ścieżkę do wierzchołka v poprzez wierzchołek u. W konsekwencji aktualizujemy odległość d[v] i ustawiamy wierzchołek u jako poprzednik p[v] dla wierzchołka v.

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class GrafDijkstra otwórz nawias klamrowy. Linia 4. static int V znak równości 7 średnik. Linia 5. static int maksymalnieSasiadow znak równości V minus 1 średnik. Linia 6. static int NIESKONCZONOSC znak równości 10000 średnik. Linia 7. static int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy listaSasiedztwa znak równości otwórz nawias klamrowy. Linia 8. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 4 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 0 otwórz nawias okrągły A zamknij nawias okrągły. Linia 9. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 4 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 6 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 1 otwórz nawias okrągły B zamknij nawias okrągły. Linia 10. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 4 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 2 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 2 otwórz nawias okrągły C zamknij nawias okrągły. Linia 11. otwórz nawias klamrowy otwórz nawias klamrowy 2 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 12 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 3 otwórz nawias okrągły D zamknij nawias okrągły. Linia 12. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 4 otwórz nawias okrągły E zamknij nawias okrągły. Linia 13. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 12 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 5 otwórz nawias okrągły F zamknij nawias okrągły. Linia 14. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 6 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 2 zamknij nawias klamrowy zamknij nawias klamrowy prawy ukośnik prawy ukośnik dla wierzcholka 6 otwórz nawias okrągły G zamknij nawias okrągły. Linia 15. zamknij nawias klamrowy średnik. Linia 17. static void Dijkstra otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy listaSasiedztwa przecinek int s zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int otwórz nawias kwadratowy zamknij nawias kwadratowy d znak równości new int otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 19. int otwórz nawias kwadratowy zamknij nawias kwadratowy p znak równości new int otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 20. boolean otwórz nawias kwadratowy zamknij nawias kwadratowy S znak równości new boolean otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 21. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości NIESKONCZONOSC średnik. Linia 23. p otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 24. zamknij nawias klamrowy. Linia 25. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 26. int odwiedzony znak równości 0 średnik. Linia 28. while otwórz nawias okrągły odwiedzony otwórz nawias ostrokątny V zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. int u znak równości minus 1 średnik. Linia 30. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy i zamknij nawias kwadratowy ampersant ampersant otwórz nawias okrągły u znak równości znak równości minus 1 kreska pionowa kreska pionowa d otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. u znak równości i średnik. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 36. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 37. odwiedzony plus plus średnik. Linia 39. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny maksymalnieSasiadow ampersant ampersant i otwórz nawias ostrokątny listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. int v znak równości listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 41. int waga znak równości listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik. Linia 44. if otwórz nawias okrągły v znak równości znak równości minus 1 zamknij nawias okrągły break średnik. Linia 46. if otwórz nawias okrągły d otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga średnik. Linia 48. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 51. zamknij nawias klamrowy. Linia 52. zamknij nawias klamrowy średnik. Linia 53. zamknij nawias klamrowy średnik.

import java.util.Arrays;

public class GrafDijkstra {
    static int V = 7;
    static int maksymalnieSasiadow = V - 1;
    static int NIESKONCZONOSC = 10000;
    static int[][][] 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)
    };

    static void Dijkstra(int[][][] listaSasiedztwa, int s) {
        int[] d = new int[V];
        int[] p = new int[V];
        boolean[] S = new boolean[V];
        for (int i = 0; i < V; i++) {
            d[i] = NIESKONCZONOSC;
            p[i] = -1;
        }
        d[s] = 0;
        int odwiedzony = 0;

        while (odwiedzony < V) {
            int u = -1;
            for (int i = 0; i < V; i++) {
                if (!S[i] && (u == -1 || d[i] < d[u])) {
                    u = i;
                }
            }

            S[u] = true;
            odwiedzony++;

            for (int i = 0; i < maksymalnieSasiadow && i < listaSasiedztwa[u].length; i++) {
                int v = listaSasiedztwa[u][i][0];
                int waga = listaSasiedztwa[u][i][1];


                if (v == -1) break;

                if (d[v] > d[u] + waga) {
                    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ą znaną 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:

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class GrafDijkstra otwórz nawias klamrowy. Linia 4. static int V znak równości 7 średnik. Linia 5. static int maksymalnieSasiadow znak równości V minus 1 średnik. Linia 6. static int NIESKONCZONOSC znak równości 10000 średnik. Linia 7. static int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy listaSasiedztwa znak równości otwórz nawias klamrowy. Linia 8. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 4 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 0 otwórz nawias okrągły A zamknij nawias okrągły. Linia 9. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 4 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 6 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 1 otwórz nawias okrągły B zamknij nawias okrągły. Linia 10. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 4 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 2 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 2 otwórz nawias okrągły C zamknij nawias okrągły. Linia 11. otwórz nawias klamrowy otwórz nawias klamrowy 2 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 12 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 3 otwórz nawias okrągły D zamknij nawias okrągły. Linia 12. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 4 otwórz nawias okrągły E zamknij nawias okrągły. Linia 13. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 12 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzcholka 5 otwórz nawias okrągły F zamknij nawias okrągły. Linia 14. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 6 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 2 zamknij nawias klamrowy zamknij nawias klamrowy prawy ukośnik prawy ukośnik dla wierzcholka 6 otwórz nawias okrągły G zamknij nawias okrągły. Linia 15. zamknij nawias klamrowy średnik. Linia 17. static void Dijkstra otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy listaSasiedztwa przecinek int s zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int otwórz nawias kwadratowy zamknij nawias kwadratowy d znak równości new int otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 19. int otwórz nawias kwadratowy zamknij nawias kwadratowy p znak równości new int otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 20. boolean otwórz nawias kwadratowy zamknij nawias kwadratowy S znak równości new boolean otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 21. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości NIESKONCZONOSC średnik. Linia 23. p otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 24. zamknij nawias klamrowy. Linia 25. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 26. int odwiedzony znak równości 0 średnik. Linia 28. while otwórz nawias okrągły odwiedzony otwórz nawias ostrokątny V zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. int u znak równości minus 1 średnik. Linia 30. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy i zamknij nawias kwadratowy ampersant ampersant otwórz nawias okrągły u znak równości znak równości minus 1 kreska pionowa kreska pionowa d otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. u znak równości i średnik. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 36. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 37. odwiedzony plus plus średnik. Linia 39. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny maksymalnieSasiadow ampersant ampersant i otwórz nawias ostrokątny listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. int v znak równości listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 41. int waga znak równości listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik. Linia 44. if otwórz nawias okrągły v znak równości znak równości minus 1 zamknij nawias okrągły break średnik. Linia 46. if otwórz nawias okrągły d otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga średnik. Linia 48. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 51. zamknij nawias klamrowy. Linia 53. System kropka out kropka print otwórz nawias okrągły cudzysłów d otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias kwadratowy cudzysłów zamknij nawias okrągły średnik. Linia 54. for otwórz nawias okrągły int value dwukropek d zamknij nawias okrągły System kropka out kropka print otwórz nawias okrągły value plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 55. System kropka out kropka println otwórz nawias okrągły cudzysłów zamknij nawias kwadratowy cudzysłów zamknij nawias okrągły średnik. Linia 57. System kropka out kropka print otwórz nawias okrągły cudzysłów p otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias kwadratowy cudzysłów zamknij nawias okrągły średnik. Linia 58. for otwórz nawias okrągły int value dwukropek p zamknij nawias okrągły System kropka out kropka print otwórz nawias okrągły value plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 59. System kropka out kropka println otwórz nawias okrągły cudzysłów zamknij nawias kwadratowy cudzysłów zamknij nawias okrągły średnik. Linia 60. zamknij nawias klamrowy. Linia 62. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 63. Dijkstra otwórz nawias okrągły listaSasiedztwa przecinek 4 zamknij nawias okrągły średnik. Linia 64. zamknij nawias klamrowy. Linia 65. zamknij nawias klamrowy.

import java.util.Arrays;

public class GrafDijkstra {
    static int V = 7;
    static int maksymalnieSasiadow = V - 1;
    static int NIESKONCZONOSC = 10000;
    static int[][][] 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)
    };

    static void Dijkstra(int[][][] listaSasiedztwa, int s) {
        int[] d = new int[V];
        int[] p = new int[V];
        boolean[] S = new boolean[V];
        for (int i = 0; i < V; i++) {
            d[i] = NIESKONCZONOSC;
            p[i] = -1;
        }
        d[s] = 0;
        int odwiedzony = 0;

        while (odwiedzony < V) {
            int u = -1;
            for (int i = 0; i < V; i++) {
                if (!S[i] && (u == -1 || d[i] < d[u])) {
                    u = i;
                }
            }

            S[u] = true;
            odwiedzony++;

            for (int i = 0; i < maksymalnieSasiadow && i < listaSasiedztwa[u].length; i++) {
                int v = listaSasiedztwa[u][i][0];
                int waga = listaSasiedztwa[u][i][1];


                if (v == -1) break;

                if (d[v] > d[u] + waga) {
                    d[v] = d[u] + waga;
                    p[v] = u;
                }
            }
        }

        System.out.print("d[] = [ ");
        for (int value : d) System.out.print(value + " ");
        System.out.println("]");

        System.out.print("p[] = [ ");
        for (int value : p) System.out.print(value + " ");
        System.out.println("]");
    }

    public static void main(String[] args) {
        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 ]

Polecenie 1

Spróbuj ręcznie zweryfikować poprawność uzyskanego rozwiązania.

Słownik

długość ścieżki (koszt dojścia)

suma wag wszystkich krawędzi, z których składa się ścieżka, droga lub cykl

graf nieskierowany

graf, którego połączone krawędziami wierzchołki nie mają ustalonego kierunku, w którym można się po nich poruszać (są nieuporządkowane)

graf spójny

graf, w którym każda para wierzchołków połączona jest drogą

graf ważony

graf którego krawędzie mają przypisane wagi

krawędź

nieuporządkowana para (niekoniecznie różnych) elementów zbioru wierzchołków, tj. takich, które są ze sobą połączone; w reprezentacji graficznej jest to linia łącząca te wierzchołki; krawędź może łączyć ze sobą jeden wierzchołek (wtedy nazywana jest pętlą)

lista sąsiedztwa

zestaw V uporządkowanych list, gdzie lista o indeksie i jest listą wszystkich sąsiadów wierzchołka i

najkrótsza ścieżka

taka ścieżka łącząca dwa wierzchołki grafu, której suma wag krawędzi jest jak najmniejsza

stopień wierzchołka

liczba krawędzi incydentnych z danym wierzchołkiem

waga krawędzi

wartość przypisana krawędzi grafu

wierzchołek

inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf

Misja: macierz sąsiedztwa

Strefa wyzwań

Implementacja algorytmu Dijkstry w języku Java

Słownik