Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

RKeBneMHltuQI

Graf jest przedstawiony z wartościami krawędzi i oznaczonymi wierzchołkami. Od wierzchołka trzy prowadzi krawędź o długości szesnaćsie do wierchołka cztery i krawędź o długości trzy do wierzchołkac zero. Od wierzchołka cztery poprowadzono ścieżkę o długości trzy do wierzchołka dwa. Od wierzchołka dwa poprowadzona jest ściezka o długości jedenascie do wierzchołka zero, o długości jeden do wierchołka pięć, o długości jeden do wierzchołka jeden. Od wierzchołka jeden krawędź od długości jeden do wierzchołka pięć. Od wierzchołka pięć do wierzchołka sześć krawędź ma długość dwanaście. Od wierzchołka sześć poprowadzona jest krawędź o długości dziesięć do wierzchołka zero. — Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

RvylmYNysQGCN

Wskaż wyniki, które algorytm Dijkstry zwróci dla przedstawionego grafu. Za wierzchołek początkowy przyjmujemy wierzchołek 3. Zaznacz wszystkie poprawne odpowiedzi.

Tablice d[] zawierają długości ścieżek do kolejnych wierzchołków, a tablice p[] – poprzedniki tych wierzchołków.

Ćwiczenie 2

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 10. 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 11. 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 12. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości NIESKONCZONOSC średnik. Linia 13. p otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 14. zamknij nawias klamrowy. Linia 16. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 17. int odwiedzony znak równości 0 średnik. Linia 19. while otwórz nawias okrągły odwiedzony otwórz nawias ostrokątny V zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. int u znak równości minus 1 ś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. Linia 22. 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 u znak równości i średnik. Linia 24. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 25. odwiedzony plus plus średnik. Linia 27. for otwórz nawias okrągły int v znak równości 0 średnik v otwórz nawias ostrokątny V średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły macierzSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny 0 ampersant ampersant wykrzyknik S otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. 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 30. 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 31. 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 32. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy. Linia 36. zamknij nawias klamrowy. Linia 37. zamknij nawias klamrowy. Linia 39. 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 40. 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 41. otwórz nawias klamrowy 0 przecinek 5 przecinek 4 przecinek 2 przecinek 7 zamknij nawias klamrowy przecinek. Linia 42. otwórz nawias klamrowy 5 przecinek 0 przecinek 1 przecinek 0 przecinek 8 zamknij nawias klamrowy przecinek. Linia 43. otwórz nawias klamrowy 4 przecinek 1 przecinek 0 przecinek 22 przecinek 4 zamknij nawias klamrowy przecinek. Linia 44. otwórz nawias klamrowy 2 przecinek 0 przecinek 22 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 45. otwórz nawias klamrowy 7 przecinek 8 przecinek 4 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 46. zamknij nawias klamrowy średnik. Linia 48. Dijkstra otwórz nawias okrągły macierzSasiedztwa przecinek 4 zamknij nawias okrągły średnik. Linia 50. 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 51. 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 52. 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 53. zamknij nawias klamrowy. 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 < 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 v = 0; v < V; v++) {
                if (macierzSasiedztwa[u][v] > 0 && !S[v]) {
                    int waga = macierzSasiedztwa[u][v];
                    if (d[v] > 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 3

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

public class GrafSciezka {
    static final int V = 5;
    static int[] p = {4, 2, 4, 0, -1};

    static void drukujSciezke(int v) {
        if (p[v] > -1) {
            drukujSciezke(p[v]);
        }
        System.out.print(v + " ");
    }

    public static void main(String[] args) {
        for (int v = 0; v < V; ++v) {
            System.out.print("Sciezka do " + v + ": ");
            drukujSciezke(v);
            System.out.println();
        }
    }
}

Ćwiczenie 4

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 5. 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 6. 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 7. 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. 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 10. otwórz nawias klamrowy 3 przecinek 4 przecinek 1 przecinek 2 przecinek 5 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 11. otwórz nawias klamrowy 0 przecinek 2 przecinek 4 przecinek 5 przecinek 3 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 12. 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 13. 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 14. otwórz nawias klamrowy 1 przecinek 2 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek. Linia 15. otwórz nawias klamrowy 1 przecinek 2 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy średnik. Linia 18. static void dijkstra otwórz nawias okrągły int s zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. for otwórz nawias okrągły int v znak równości 0 średnik v otwórz nawias ostrokątny V średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości NIESKONCZONOSC średnik. Linia 21. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 22. S otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości false średnik. Linia 23. zamknij nawias klamrowy. Linia 24. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 25. int odwiedzony znak równości 0 średnik. Linia 27. while otwórz nawias okrągły odwiedzony otwórz nawias ostrokątny V zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. int u znak równości minus 1 średnik. Linia 29. for otwórz nawias okrągły int v znak równości 0 średnik v otwórz nawias ostrokątny V średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy v 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 v 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 31. u znak równości v średnik. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 35. 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 36. break średnik. Linia 37. zamknij nawias klamrowy. Linia 39. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 40. odwiedzony plus plus średnik. Linia 42. 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 43. 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 44. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant ampersant d otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 45. 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 46. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 47. zamknij nawias klamrowy. Linia 48. zamknij nawias klamrowy. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 52. 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 53. dijkstra otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 55. 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 56. 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 57. 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 58. 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 59. zamknij nawias klamrowy. Linia 60. 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 62. 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 63. 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 64. 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 65. zamknij nawias klamrowy. Linia 66. 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 67. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 68. zamknij nawias klamrowy. 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 < V; v++) {
            d[v] = NIESKONCZONOSC;
            p[v] = -1;
            S[v] = false;
        }
        d[s] = 0;
        int odwiedzony = 0;

        while (odwiedzony < V) {
            int u = -1;
            for (int v = 0; v < V; v++) {
                if (!S[v] && (u == -1 || d[v] < 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] && d[v] > 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 < V; i++) {
            System.out.print(d[i] + " ");
        }
        System.out.println("}");

        System.out.print("p[] = {");
        for (int i = 0; i < V; i++) {
            System.out.print(p[i] + " ");
        }
        System.out.println("}");
        System.out.println();
    }
}

R9uCikLPk8IBR31

Ćwiczenie 5

Możliwe odpowiedzi: 1. d = [ 0 7 10 10 8 12 10 9 ]
prev = [ -1 3 1 4 1 7 1 0 ], 2. d = [ 0 7 10 10 8 12 10 9 ]
prev = [ -1 0 1 4 1 7 1 0 ], 3. d = [ 0 11 10 10 8 12 10 9 ]
prev = [ -1 0 1 4 1 7 1 0 ], 4. d = [ 12 5 3 2 4 0 4 3 ]
prev = [ 7 4 5 5 3 -1 7 5 ]

Ćwiczenie 6

R1Hg0lizxV4dc31

Oznacz wagi krawędzi dla przedstawionego grafu, jeśli wiadomo, że algorytm Dijkstry dla pewnego wierzchołka zwrócił następujące wyniki:

d[] = {28, 17, 30, 35, 0, 16}
p[] = {1, 4, 5, 1, -1, 4}

Tablica d[] zawiera długości ścieżek do kolejnych wierzchołków, a tablica p[] – poprzedniki tych wierzchołków.

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

Ćwiczenie 6

RiUMFpRjG1lYX

Prezentacja multimedialna

Dla nauczyciela