Strefa wyzwań - I_R_W14_M38_Java Podejście zachłanne. Najkrótsza droga w grafie

R1GJG6M5BA9OA

Już wiesz

jak działa podejście zachłanne i potrafisz wskazać, w którym momencie algorytm Dijkstry podejmuje lokalnie najlepszą decyzję,
umiesz przeanalizować kolejne kroki algorytmu na grafie ważonym, odczytać wartości w tablicach d i p oraz określić, kiedy wierzchołek zostaje oznaczony jako „odwiedzony”,
potrafisz przełożyć pseudokod na działający program w Javie, uruchomić go na przykładzie i zinterpretować otrzymane wyniki,
wiesz jak zmodyfikować implementację, aby działała dla różnych reprezentacji grafów.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce.

R1MLBVSD4PJ2V

Ćwiczenie 1

RPJL89HVFXUCA

Ćwiczenie 2

Ćwiczenie 3

Zapoznaj się z pseudokodem.

Dijkstra(lista_sąsiedztwa, s):
	S ← utwórz pustą tablicę
    V ← utwórz tablicę i wypełnij ją wierzchołkami
    d ← utwórz pustą tablicę
    p ← utwórz pustą tablicę
    
	dla każdego elementu u w tablicy V:
		d[u] ← ∞
		p[u] ← -1
        
	d[s] ← 0
    
	dopóki długość(V) > 0:
		najkrótsza_ścieżka ← ∞
		u ← -1
        
		dla każdego elementu v w tablicy V:
			jeśli najkrótsza_ścieżka > d[v]:
				najkrótsza_ścieżka ← d[v]
				u ← v
                
		S ← umieść element u na końcu tablicy
        V ← usuń element u z tablicy
        
		dla każdego elementu v w tablicy lista_sąsiadów[u]:
			jeśli d[v] > d[u] + w(u, v):
				d[v] ← d[u] + w(u, v)
				p[v] ← u
    
	zwróć d, p

RT1XEV2L8ES4H

Połącz w pary zmienne z ich zastosowaniami. prev[] Możliwe odpowiedzi: 1. wierzchołek dodawany do zbioru S unikalny dla każdej iteracji, 2. zbiór wszystkich wierzchołków grafu, 3. tablica kosztów dojścia do każdego wierzchołka, 4. zbiór wierzchołków, do których najmniejsze koszty dojścia zostały wyznaczone, 5. tablica przechowująca poprzedniki wierzchołków d[] Możliwe odpowiedzi: 1. wierzchołek dodawany do zbioru S unikalny dla każdej iteracji, 2. zbiór wszystkich wierzchołków grafu, 3. tablica kosztów dojścia do każdego wierzchołka, 4. zbiór wierzchołków, do których najmniejsze koszty dojścia zostały wyznaczone, 5. tablica przechowująca poprzedniki wierzchołków u Możliwe odpowiedzi: 1. wierzchołek dodawany do zbioru S unikalny dla każdej iteracji, 2. zbiór wszystkich wierzchołków grafu, 3. tablica kosztów dojścia do każdego wierzchołka, 4. zbiór wierzchołków, do których najmniejsze koszty dojścia zostały wyznaczone, 5. tablica przechowująca poprzedniki wierzchołków S Możliwe odpowiedzi: 1. wierzchołek dodawany do zbioru S unikalny dla każdej iteracji, 2. zbiór wszystkich wierzchołków grafu, 3. tablica kosztów dojścia do każdego wierzchołka, 4. zbiór wierzchołków, do których najmniejsze koszty dojścia zostały wyznaczone, 5. tablica przechowująca poprzedniki wierzchołków V Możliwe odpowiedzi: 1. wierzchołek dodawany do zbioru S unikalny dla każdej iteracji, 2. zbiór wszystkich wierzchołków grafu, 3. tablica kosztów dojścia do każdego wierzchołka, 4. zbiór wierzchołków, do których najmniejsze koszty dojścia zostały wyznaczone, 5. tablica przechowująca poprzedniki wierzchołków

Ćwiczenie 4

RP2XD5J1MVU3111

Graf składa się z pięciu wierzchołków. Tworzą one pięciokąt. Od wierzchołka jeden poprowadzone są dwie strzałki stanowiące krawędzie. Pierwsza o długości trzy prowadzi do wierzchołka zero, natomiast druga o długości dwa do wierzchołka dwa. Od wierzchołka dwa do wierzchołka cztery poprowadzona jest strzałka stanowiąca krawędź o długości siedem. Od wierzchołka zero do wierzchołka trzy poprowadzona jest strzałka odpowiadająca krawędzi o długości pięć. Od wierzchołka trzy do wierzchołka cztery poprowadzona jest strzałka stanowiąca krawędź o długości jeden. Od wierzchołka cztery do wierzchołka jeden poprowadzona jest strzałka odpowiadająca krawędzi o długości dziesięć.

Zapoznaj się z ilustracją pewnego grafu.

R1DDB6QHO9RG2

Wskaż wszystkie warianty tablic wyjściowych d i p, które może zwrócić algorytm Dijkstry dla zaprezentowanego grafu skierowanego.

Ćwiczenie 5

R14SS7ECZKDJ1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

R24L74X7MLD1E

Przyjmując za wierzchołek początkowy A, wskaż grafy, dla których algorytm Dijkstry nie zwróci poprawnego wyniku.

Ćwiczenie 6

RU821QGJCCM6E

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

R1JZR8G6446TH

Zapoznaj się poniższym opisem, a następnie wykonaj polecenie.
Graf składa się z sześciu wierzchołków oznaczonych od A do F. Wierzchołki połączone są krawędziami, tworzacymi sześciokąt. Ponadto dwie krawędzie zostały zaznaczone pomiędzy wierzchołkami wten sposób, że znajdują się w polu sześciokąta. Od wierzchołka A popdorwadzone sa dwie krawędzie do wierzchołka B o długości dziesięć i do wierzchołka C o długości sześć. Od wierzchołka B odchodzą dwie krawędzie. Pierwsza o długości cztery łączy go z wierzhcołkiem E, natomiast druga o długości dwa z wierzchołkiem F.Od wierzchołka C odchodzą dwie krawędzie. Pierwsza o długości siedem łączy wierzchołek C z wierzchołkiem D, natomiast druga o długości pięć z wierzchołkiem F. Warości dla krawędzi łączących odpowiednio wierzchołki D F oraz E F nie podano.
Wskaż długości ścieżek łączących, odpowiednio wierzchołki D F oraz E F, aby algorytm Dijkstry zwrócił następujący wynik:

d = { 6, 7, 0, 7, 6, 5 }, 
 p = { C, F, NULL, C, F, C }

Materiał źródłowy do ćwiczeń 7–8

R1V7E6DUR1ERT

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

R4TUMFGLKNNP6

Ćwiczenie 7

W zaprezentowanym grafie s = E. Wskaż poprzednika, jeśli u = A.

RRZTEEDTNXPZ7

Ćwiczenie 8

W zaprezentowanym grafie s = A. Wskaż poprawną długość najkrótszej ścieżki, jaką należy pokonać, by od wierzchołka s dojść do wierzchołka u = B.

Polecenie 1

Zapisz program z polecenia nr 1, używając wybranego języka programowania.

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

RXGBR4F91RSKB

Specyfikacja problemu:

Dane:

lista_sąsiedztwa – lista sąsiedztwa grafu nieskierowanego o dodatnich wagach
s – wierzchołek początkowy grafu

Wynik:

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

R1N49QCGLFANU

Ćwiczenie 9

Napisz program, który dla grafu reprezentowanego przez macierz sąsiedztwa wypisze dwie tablice – najkrótszych ścieżek do danych wierzchołków oraz poprzedników tych wierzchołków.

Działanie programu przetestuj dla następujących danych:

int[][] macierzSasiedztwa = {
	{ 0, 5, 4, 2, 7 },
	{ 5, 0, 1, 0, 8 },
	{ 4, 1, 0, 22, 4 },
	{ 2, 0, 22, 0, 0 },
	{ 7, 8, 4, 0, 0 }
};

int s = 4;

Specyfikacja problemu:

Dane:

s – wierzchołek początkowy grafu
macierzSasiedztwa – tablica dwuwymiarowa; macierz sąsiedztwa 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

Wynik dla podanych danych:

Wynik algorytmu Dijkstry:
d[] = [7, 5, 4, 9, 0]
p[] = [4, 2, 4, 0, -1]

R1DQ5xS7JpnoT

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class DijkstraAlgorytm otwórz nawias klamrowy. Linia 4. public static final int V znak równości 5 średnik. Linia 5. public static final int NIESKONCZONOSC znak równości 10000 średnik. Linia 6. public static 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 7. public static 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 8. public static 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 9. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny public static void Dijkstra otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy macierzSasiedztwa przecinek int s zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości NIESKONCZONOSC średnik. Linia 12. p otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 13. zamknij nawias klamrowy. Linia 15. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 16. int odwiedzony znak równości 0 średnik. Linia 18. while otwórz nawias okrągły odwiedzony ampersant lt średnik V zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. int u znak równości minus 1 średnik. Linia 20. for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik V średnik i plus plus zamknij nawias okrągły. Linia 21. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy i zamknij nawias kwadratowy ampersant amp średnik ampersant amp średnik 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 ampersant lt średnik d otwórz nawias kwadratowy u zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły u znak równości i średnik. Linia 23. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 24. odwiedzony plus plus średnik. Linia 26. for otwórz nawias okrągły int v znak równości 0 średnik v ampersant lt średnik V średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. if otwórz nawias okrągły macierzSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant gt średnik 0 ampersant amp średnik ampersant amp średnik wykrzyknik S otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. int waga znak równości macierzSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy średnik. Linia 29. if otwórz nawias okrągły d otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant gt średnik d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. 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 31. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy. Linia 36. zamknij nawias klamrowy. Linia 38. 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 39. int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy macierzSasiedztwa znak równości otwórz nawias klamrowy. Linia 40. otwórz nawias klamrowy 0 przecinek 5 przecinek 4 przecinek 2 przecinek 7 zamknij nawias klamrowy przecinek. Linia 41. otwórz nawias klamrowy 5 przecinek 0 przecinek 1 przecinek 0 przecinek 8 zamknij nawias klamrowy przecinek. Linia 42. otwórz nawias klamrowy 4 przecinek 1 przecinek 0 przecinek 22 przecinek 4 zamknij nawias klamrowy przecinek. Linia 43. otwórz nawias klamrowy 2 przecinek 0 przecinek 22 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 44. otwórz nawias klamrowy 7 przecinek 8 przecinek 4 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 45. zamknij nawias klamrowy średnik. Linia 47. Dijkstra otwórz nawias okrągły macierzSasiedztwa przecinek 4 zamknij nawias okrągły średnik. Linia 49. System kropka out kropka println otwórz nawias okrągły cudzysłów Wynik algorytmu Dijkstry dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 50. System kropka out kropka println otwórz nawias okrągły cudzysłów d otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości cudzysłów plus Arrays kropka toString otwórz nawias okrągły d zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 51. System kropka out kropka println otwórz nawias okrągły cudzysłów p otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości cudzysłów plus Arrays kropka toString otwórz nawias okrągły p zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 52. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 54. zamknij nawias klamrowy.

import java.util.Arrays;

public class DijkstraAlgorytm {
public static final int V = 5;
public static final int NIESKONCZONOSC = 10000;
public static int[] d = new int[V];
public static int[] p = new int[V];
public static boolean[] S = new boolean[V];
    public static void Dijkstra(int[][] macierzSasiedztwa, int s) {
        for (int i = 0; i &lt; V; i++) {
            d[i] = NIESKONCZONOSC;
            p[i] = -1;
        }        
    
        d[s] = 0;
        int odwiedzony = 0;
    
        while (odwiedzony &lt; V) {
            int u = -1;
            for (int i = 0; i &lt; V; i++)
                if (!S[i] &amp;&amp; (u == -1 || d[i] &lt; d[u])) u = i;
    
            S[u] = true;
            odwiedzony++;
    
            for (int v = 0; v &lt; V; v++) {
                if (macierzSasiedztwa[u][v] &gt; 0 &amp;&amp; !S[v]) {
                    int waga = macierzSasiedztwa[u][v];
                    if (d[v] &gt; d[u] + waga) {
                        d[v] = d[u] + waga;
                        p[v] = u;
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[][] macierzSasiedztwa = {
            {0, 5, 4, 2, 7},
            {5, 0, 1, 0, 8},
            {4, 1, 0, 22, 4},
            {2, 0, 22, 0, 0},
            {7, 8, 4, 0, 0}
        };
    
        Dijkstra(macierzSasiedztwa, 4);
    
        System.out.println("Wynik algorytmu Dijkstry:");
        System.out.println("d[] = " + Arrays.toString(d));
        System.out.println("p[] = " + Arrays.toString(p));
    }

}

Ćwiczenie 10

Napisz program, który dla danej tablicy poprzedników grafu wypisze kompletne ścieżki do kolejnych wierzchołków. Ścieżki powinny zaczynać się w wierzchołku początkowym, a kończyć na docelowym.

Działanie programu przetestuj dla następujących danych:

static int[] p = {4, 2, 4, 0, -1};

Specyfikacja problemu:

Dane:

p – tablica poprzedników; tablica liczb całkowitych
V – liczba naturalna dodatnia; liczba wierzchołków grafu

Wynik:

komunikat dotyczący najkrótszych ścieżek do kolejnych wierzchołków

Wynik dla podanych danych:

Sciezka do 0: 4 0 
Sciezka do 1: 4 2 1 
Sciezka do 2: 4 2 
Sciezka do 3: 4 0 3 
Sciezka do 4: 4

RcQqJn364Py1r

Linia 1. public class GrafSciezka otwórz nawias klamrowy. Linia 2. static final int V znak równości 5 średnik. Linia 3. static int otwórz nawias kwadratowy zamknij nawias kwadratowy p znak równości otwórz nawias klamrowy 4 przecinek 2 przecinek 4 przecinek 0 przecinek minus 1 zamknij nawias klamrowy średnik. Linia 4. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny static void drukujSciezke otwórz nawias okrągły int v zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. if otwórz nawias okrągły p otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant gt średnik minus 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. drukujSciezke otwórz nawias okrągły p otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 7. zamknij nawias klamrowy. Linia 8. System kropka out kropka print otwórz nawias okrągły v plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 9. zamknij nawias klamrowy. Linia 11. 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 12. for otwórz nawias okrągły int v znak równości 0 średnik v ampersant lt średnik V średnik plus plus v zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. System kropka out kropka print otwórz nawias okrągły cudzysłów Sciezka do cudzysłów plus v plus cudzysłów dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 14. drukujSciezke otwórz nawias okrągły v zamknij nawias okrągły średnik. Linia 15. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 19. zamknij nawias klamrowy.

public class GrafSciezka {
    static final int V = 5;
    static int[] p = {4, 2, 4, 0, -1};
    static void drukujSciezke(int v) {
        if (p[v] &gt; -1) {
            drukujSciezke(p[v]);
        }
        System.out.print(v + " ");
    }
    
    public static void main(String[] args) {
        for (int v = 0; v &lt; V; ++v) {
            System.out.print("Sciezka do " + v + ": ");
            drukujSciezke(v);
            System.out.println();
        }
    }

}

Ćwiczenie 11

Zmodyfikuj program tak, by algorytm Dijkstry działał dla grafu, którego każda krawędź ma wagę równą 1.

Działanie programu przetestuj dla następujących danych:

static final int[][] listaSasiedztwa = {
	{3, 4, 1, 2, 5, -1},
	{0, 2, 4, 5, 3, -1},
	{3, -1, -1, -1, -1, -1},
	{5, -1, -1, -1, -1, -1},
	{1, 2, -1, -1, -1, -1},
	{1, 2, -1, -1, -1, -1}
};

int s = 4;

Specyfikacja problemu:

Dane:

listaSasiedztwa – tablica dwuwymiarowa; lista sąsiedztwa grafu
s – wierzchołek początkowy 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

Wynik dla podanych danych:

Wynik algorytmu Dijkstry:
d[] = {2 1 1 2 0 2 }
p[] = {1 4 4 1 -1 1 }

R1GzFwk63Rmpb

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. static final int V znak równości 6 średnik. Linia 3. static final int NIESKONCZONOSC znak równości 10000 średnik. Linia 4. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny static 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 5. static 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 6. static 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 8. static int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy listaSasiedztwa znak równości otwórz nawias klamrowy. Linia 9. otwórz nawias klamrowy 3 przecinek 4 przecinek 1 przecinek 2 przecinek 5 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 10. otwórz nawias klamrowy 0 przecinek 2 przecinek 4 przecinek 5 przecinek 3 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 11. otwórz nawias klamrowy 3 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 12. otwórz nawias klamrowy 5 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 13. otwórz nawias klamrowy 1 przecinek 2 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 14. otwórz nawias klamrowy 1 przecinek 2 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy średnik. Linia 17. static void dijkstra otwórz nawias okrągły int s zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. for otwórz nawias okrągły int v znak równości 0 średnik v ampersant lt średnik V średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości NIESKONCZONOSC średnik. Linia 20. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 21. S otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości false średnik. Linia 22. zamknij nawias klamrowy. Linia 23. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 24. int odwiedzony znak równości 0 średnik. Linia 26. while otwórz nawias okrągły odwiedzony ampersant lt średnik V zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. int u znak równości minus 1 średnik. Linia 28. for otwórz nawias okrągły int v znak równości 0 średnik v ampersant lt średnik V średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant amp średnik ampersant amp średnik 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 v zamknij nawias kwadratowy ampersant lt średnik d otwórz nawias kwadratowy u zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. u znak równości v średnik. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 34. if otwórz nawias okrągły d otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości znak równości NIESKONCZONOSC zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. break średnik. Linia 36. zamknij nawias klamrowy. Linia 38. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 39. odwiedzony plus plus średnik. Linia 41. for otwórz nawias okrągły int i znak równości 0 średnik listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. int v znak równości listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 43. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant amp średnik ampersant amp średnik d otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant gt średnik d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus 1 średnik. Linia 45. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 46. zamknij nawias klamrowy. Linia 47. zamknij nawias klamrowy. Linia 48. zamknij nawias klamrowy. Linia 49. zamknij nawias klamrowy. Linia 51. 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 52. dijkstra otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 54. System kropka out kropka println otwórz nawias okrągły cudzysłów Wynik algorytmu Dijkstry dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 55. 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 klamrowy cudzysłów zamknij nawias okrągły średnik. Linia 56. for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. System kropka out kropka print otwórz nawias okrągły d otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 58. zamknij nawias klamrowy. Linia 59. System kropka out kropka println otwórz nawias okrągły cudzysłów zamknij nawias klamrowy cudzysłów zamknij nawias okrągły średnik. Linia 61. 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 klamrowy cudzysłów zamknij nawias okrągły średnik. Linia 62. for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 63. System kropka out kropka print otwórz nawias okrągły p otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 64. zamknij nawias klamrowy. Linia 65. System kropka out kropka println otwórz nawias okrągły cudzysłów zamknij nawias klamrowy cudzysłów zamknij nawias okrągły średnik. Linia 66. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 67. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 69. zamknij nawias klamrowy.

public class Main {
    static final int V = 6;
    static final int NIESKONCZONOSC = 10000;
    static int[] d = new int[V];
    static int[] p = new int[V];
    static boolean[] S = new boolean[V];
    
    static int[][] listaSasiedztwa = {
        {3, 4, 1, 2, 5, -1},
        {0, 2, 4, 5, 3, -1},
        {3, -1, -1, -1, -1, -1},
        {5, -1, -1, -1, -1, -1},
        {1, 2, -1, -1, -1, -1},
        {1, 2, -1, -1, -1, -1}
    };
    
    static void dijkstra(int s) {
        for (int v = 0; v &lt; V; v++) {
            d[v] = NIESKONCZONOSC;
            p[v] = -1;
            S[v] = false;
        }
        d[s] = 0;
        int odwiedzony = 0;
    
        while (odwiedzony &lt; V) {
            int u = -1;
            for (int v = 0; v &lt; V; v++) {
                if (!S[v] &amp;&amp; (u == -1 || d[v] &lt; d[u])) {
                    u = v;
                }
            }
    
            if (d[u] == NIESKONCZONOSC) {
                break;
            }
    
            S[u] = true;
            odwiedzony++;
    
            for (int i = 0; listaSasiedztwa[u][i] != -1; i++) {
                int v = listaSasiedztwa[u][i];
                if (!S[v] &amp;&amp; d[v] &gt; d[u] + 1) {
                    d[v] = d[u] + 1;
                    p[v] = u;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        dijkstra(4);
    
        System.out.println("Wynik algorytmu Dijkstry:");
        System.out.print("d[] = {");
        for (int i = 0; i &lt; V; i++) {
            System.out.print(d[i] + " ");
        }
        System.out.println("}");
    
        System.out.print("p[] = {");
        for (int i = 0; i &lt; V; i++) {
            System.out.print(p[i] + " ");
        }
        System.out.println("}");
        System.out.println();
    }

}

Implementacja

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