Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

R6dOpb2dYiDpP

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

RHA1KOxRv8qQ5

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.
Opis grafu:
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.

Ć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:

macierz_sasiedztwa = [
    [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]
]

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]

RxlJrSzIDLmTz

Linia 1. V znak równości 5. Linia 2. nieskonczonosc znak równości 10000. Linia 3. d znak równości otwórz nawias kwadratowy nieskonczonosc zamknij nawias kwadratowy asterysk V. Linia 4. p znak równości otwórz nawias kwadratowy minus 1 zamknij nawias kwadratowy asterysk V. Linia 5. S znak równości otwórz nawias kwadratowy False zamknij nawias kwadratowy asterysk V. Linia 7. def dijkstra otwórz nawias okrągły macierz podkreślnik sasiedztwa przecinek s zamknij nawias okrągły dwukropek. Linia 8. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0. Linia 9. odwiedzony znak równości 0. Linia 11. while odwiedzony otwórz nawias ostrokątny V dwukropek. Linia 12. u znak równości minus 1. Linia 13. for i in range otwórz nawias okrągły V zamknij nawias okrągły dwukropek. Linia 14. if not S otwórz nawias kwadratowy i zamknij nawias kwadratowy and otwórz nawias okrągły u znak równości znak równości minus 1 or 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 dwukropek. Linia 15. u znak równości i. Linia 17. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości True. Linia 18. odwiedzony plus znak równości 1. Linia 20. for v in range otwórz nawias okrągły V zamknij nawias okrągły dwukropek. Linia 21. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny 0 and not S otwórz nawias kwadratowy v zamknij nawias kwadratowy dwukropek. Linia 22. waga znak równości macierz podkreślnik sasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy. Linia 23. if d otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga dwukropek. Linia 24. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga. Linia 25. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u. Linia 27. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 28. otwórz nawias kwadratowy 0 przecinek 5 przecinek 4 przecinek 2 przecinek 7 zamknij nawias kwadratowy przecinek. Linia 29. otwórz nawias kwadratowy 5 przecinek 0 przecinek 1 przecinek 0 przecinek 8 zamknij nawias kwadratowy przecinek. Linia 30. otwórz nawias kwadratowy 4 przecinek 1 przecinek 0 przecinek 22 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 31. otwórz nawias kwadratowy 2 przecinek 0 przecinek 22 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 32. otwórz nawias kwadratowy 7 przecinek 8 przecinek 4 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 33. zamknij nawias kwadratowy. Linia 35. dijkstra otwórz nawias okrągły macierz podkreślnik sasiedztwa przecinek 4 zamknij nawias okrągły. Linia 37. print otwórz nawias okrągły cudzysłów Wynik algorytmu Dijkstry dwukropek cudzysłów zamknij nawias okrągły. Linia 38. print otwórz nawias okrągły cudzysłów d znak równości cudzysłów przecinek d zamknij nawias okrągły. Linia 39. print otwórz nawias okrągły cudzysłów p znak równości cudzysłów przecinek p zamknij nawias okrągły.

V = 5
nieskonczonosc = 10000
d = [nieskonczonosc] * V
p = [-1] * V
S = [False] * V

def dijkstra(macierz_sasiedztwa, s):
    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

        S[u] = True
        odwiedzony += 1

        for v in range(V):
            if macierz_sasiedztwa[u][v] > 0 and not S[v]:
                waga = macierz_sasiedztwa[u][v]
                if d[v] > d[u] + waga:
                    d[v] = d[u] + waga
                    p[v] = u

macierz_sasiedztwa = [
    [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(macierz_sasiedztwa, 4)

print("Wynik algorytmu Dijkstry:")
print("d =", d)
print("p =", 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:

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

RUcV1h2yWm5oe

Ć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:

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]
]

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]

R1INEcx1lqj7z

Linia 1. V znak równości 6. Linia 2. NIESKONCZONOSC znak równości 10000. Linia 4. d znak równości otwórz nawias kwadratowy NIESKONCZONOSC zamknij nawias kwadratowy asterysk V. Linia 5. p znak równości otwórz nawias kwadratowy minus 1 zamknij nawias kwadratowy asterysk V. Linia 6. S znak równości otwórz nawias kwadratowy False zamknij nawias kwadratowy asterysk V. Linia 8. lista podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 9. otwórz nawias kwadratowy 3 przecinek 4 przecinek 1 przecinek 2 przecinek 5 przecinek minus 1 zamknij nawias kwadratowy przecinek. Linia 10. otwórz nawias kwadratowy 0 przecinek 2 przecinek 4 przecinek 5 przecinek 3 przecinek minus 1 zamknij nawias kwadratowy przecinek. Linia 11. otwórz nawias kwadratowy 3 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias kwadratowy przecinek. Linia 12. otwórz nawias kwadratowy 5 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias kwadratowy przecinek. Linia 13. otwórz nawias kwadratowy 1 przecinek 2 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias kwadratowy przecinek. Linia 14. otwórz nawias kwadratowy 1 przecinek 2 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias kwadratowy. Linia 15. zamknij nawias kwadratowy. Linia 17. def dijkstra otwórz nawias okrągły s zamknij nawias okrągły dwukropek. Linia 18. for v in range otwórz nawias okrągły V zamknij nawias okrągły dwukropek. Linia 19. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości NIESKONCZONOSC. Linia 20. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości minus 1. Linia 21. S otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości False. Linia 22. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0. Linia 23. odwiedzony znak równości 0. Linia 25. while odwiedzony otwórz nawias ostrokątny V dwukropek. Linia 26. u znak równości minus 1. Linia 27. for v in range otwórz nawias okrągły V zamknij nawias okrągły dwukropek. Linia 28. if not S otwórz nawias kwadratowy v zamknij nawias kwadratowy and otwórz nawias okrągły u znak równości znak równości minus 1 or 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 dwukropek. Linia 29. u znak równości v. Linia 31. if d otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości znak równości NIESKONCZONOSC dwukropek. Linia 32. break. Linia 34. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości True. Linia 35. odwiedzony plus znak równości 1. Linia 37. for i in lista podkreślnik sasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy dwukropek. Linia 38. if i znak równości znak równości minus 1 dwukropek. Linia 39. break. Linia 40. if not S otwórz nawias kwadratowy i zamknij nawias kwadratowy and d otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus 1 dwukropek. Linia 41. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus 1. Linia 42. p otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości u. Linia 44. dijkstra otwórz nawias okrągły 4 zamknij nawias okrągły. Linia 45. print otwórz nawias okrągły cudzysłów Wynik algorytmu Dijkstry dwukropek cudzysłów zamknij nawias okrągły. Linia 46. print otwórz nawias okrągły cudzysłów d znak równości cudzysłów przecinek d zamknij nawias okrągły. Linia 47. print otwórz nawias okrągły cudzysłów p znak równości cudzysłów przecinek p zamknij nawias okrągły.

V = 6
NIESKONCZONOSC = 10000

d = [NIESKONCZONOSC] * V
p = [-1] * V
S = [False] * V

lista_sasiedztwa = [
    [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]
]

def dijkstra(s):
    for v in range(V):
        d[v] = NIESKONCZONOSC
        p[v] = -1
        S[v] = False
    d[s] = 0
    odwiedzony = 0

    while odwiedzony < V:
        u = -1
        for v in range(V):
            if not S[v] and (u == -1 or d[v] < d[u]):
                u = v

        if d[u] == NIESKONCZONOSC:
            break

        S[u] = True
        odwiedzony += 1

        for i in lista_sasiedztwa[u]:
            if i == -1:
                break
            if not S[i] and d[i] > d[u] + 1:
                d[i] = d[u] + 1
                p[i] = u

dijkstra(4)
print("Wynik algorytmu Dijkstry:")
print("d = ",d)
print("p = ",p)

RSFUEmIyx9mMx31

Ćwiczenie 5

Ćwiczenie 6

RXSCqeGvRo3J831

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.

RKMm45nPHJNek

Wskaż wagę ostatniej krawędzi dla opisanego 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.Graf składa się z sześciu wierzchołków. U dołu od wierzchołka zero poprowadzona linia pozioma do wierzchołka jeden to krawędź o wadze równej jedenaście. Od wierzchołka jeden linia pionowa, do góry do wierzchołka cztery to krawędź o wadze siedemnaście. Od wierzchołka cztery pozioma linia poprowadzona w lewo do wierzchołka pięć to krawędź o wadze szesnaście. Dalej od wierzchołka pięć do wierzchołka dwa, znajdującego się po prawej stronie na wysokości wierzchołków zero i jeden, poprowadzona jest krawędź o wadze czternaście. Od wierzchołka dwa linia pionowa poprowadzona do góry, pionowo do wierzchołka trzy to krawędź o wadze dziewiętnaście. Od wierzchołka trzy linia poprowadzona jest po skosie w dół do wierzchołka jeden. To ostatnia krawędź o wadze równej...

Prezentacja multimedialna

Dla nauczyciela