Strefa wyzwań

RC7RTMQOH6TRX

Ćwiczenie 1

RGEZ6FB9GN3NO

Ć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

RFUFDGA2BBL3P

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

RF612ZSS2KM1Z11

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.

R18LMEFOEE5BC

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

Ćwiczenie 5

R574NO8DKQQ29

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

R22E6OCXKBJJJ

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

Ćwiczenie 6

R1CDZM4UUXUU9

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

RUBKJ6DS2FTK8

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

RXMZZS7V9OPHB

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.

RUA58OHSUHKHM

Ćwiczenie 7

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

R1ANDR89NCHHH

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

Ćwiczenie 9

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.

RSFUEmIyx9mMx31

Ćwiczenie 10

Ćwiczenie 11

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

Misja: Ćwicz i zwyciężaj