Zapisz pseudokod programu, który dla spójnego ważonego grafu nieskierowanego o dodatnich wagach reprezentowanego przez listę sąsiedztwa wyświetli tablicę najkrótszych ścieżek prowadzących do kolejnych wierzchołków z wierzchołka początkowego oraz poprzedniki tych wierzchołków.

Specyfikacja problemu:

Dane:

• lista_sąsiedztwa – lista sąsiedztwa spójnego grafu nieskierowanego o dodatnich wagach

• s – wierzchołek początkowy grafu

Wynik:

• tablica przechowujące najkrótsze ścieżki od wierzchołka s do pozostałych wierzchołków oraz tablica przechowująca poprzedniki kolejnych wierzchołków

Zapoznaj się z prezentacją multimedialną przedstawiającą pseudokod algorytmu Dijkstry.

Zapisz program z polecenia nr 1, używając wybranego języka programowania.

Działanie programu przetestuj dla następującego grafu:

R9MyDgEmZGO5Z

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.

Specyfikacja problemu:

Dane:

• lista_sąsiedztwa – lista sąsiedztwa grafu nieskierowanego o dodatnich wagach

• s – wierzchołek początkowy grafu

Wynik:

• tablica przechowujące najkrótsze ścieżki od wierzchołka s do pozostałych wierzchołków oraz tablica przechowująca poprzedniki kolejnych wierzchołków