Prezentacja multimedialna

Polecenie 1

Zapisz program, który dla grafu reprezentowanego przez macierz sąsiedztwa wypisze najkrótszą ścieżkę prowadzącą od danego wierzchołka początkowego s do wierzchołka docelowego k.

Działanie programu przetestuj 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.

Macierz sąsiedztwa tego grafu:

int macierzSasiedztwa[V][V] = {
	{0, 1, 4, 0, 0, 0, 0},
	{1, 0, 0, 0, 1, 3, 6},
	{4, 0, 0, 5, 0, 0, 2},
	{0, 0, 5, 0, 0, 12, 0},
	{0, 1, 0, 0, 0, 0, 0},
	{0, 3, 0, 12, 0, 0, 0},
	{0, 6, 2, 0, 0, 0, 0}
};

Za wierzchołek początkowy przyjmij wierzchołek A (o indeksie 0), a za wierzchołek docelowy – wierzchołek G (o indeksie 6).

Specyfikacja problemu:

Dane:

macierzSasiedztwa – macierz sąsiedztwa spójnego grafu nieskierowanego o dodatnich wagach
s – indeks wierzchołka początkowego grafu
k – indeks wierzchołka docelowego grafu
V – liczba naturalna dodatnia; liczba wierzchołków grafu
Wynik:
odpowiedni komunikat, który informuje o najkrótszej ścieżce od wierzchołka s, jej długości i przebiegu, albo o tym, że takiej ścieżki nie ma

Przykładowy wynik dla podanych danych:

Najkrótsza ścieżka od wierzchołka 0 do wierzchołka 6 ma długość: 6

RY32RxXo1V2kw

Polecenie 2

Zapoznaj się z prezentacją przedstawiającą program, który wykorzystuje algorytm Dijkstry do odnalezienia najkrótszej ścieżki od wierzchołka początkowge do innego wierzchołka w grafie reprezentowanym przez macierz sąsiedztwa.

R19PKJqtwlVAI1

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

Polecenie 3

RCmtupnmMawYD

Przeczytaj

Sprawdź się