Misja: Ćwicz i zwyciężaj

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:

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

R5SMHLFG41HLT

Polecenie 2

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

RozQ2ZgXiUqx21

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

Implementacja algorytmu Dijkstry

Strefa wyzwań