Moduł
Implementacja funkcji znajdującej najkrótszą drogę dla danego grafu (algorytm Dijkstry). Należy samemu opracować strukturę danych i jak będzie kodowany graf.
Graf może być kodowany jako macierz wag w, gdzie element w(i,j) informuje o wadze pomiędzy wierzchołkiem „i” a „j”. Domyślnie proszę przyjąć, że celem jest wyznaczenie odległości pomiędzy wierzchołkiem „1” a „n”. Gdzie n to ilość wierzchołków.
Wejście: zakodowana postać grafu
Wyjście: ciąg wierzchołków opisujących najkrótszą ścieżkę oraz jej długość
Moduł funkcja generująca losowy graf (o nieujemnych wagach) o n (parametr) wierzchołkach. Warunkiem jest brak połączenia pomiędzy 1 a n wierzchołkiem.
2a (dla chętnych) – prośba uwzględnienie warunku na brak połączenia o długości 2.
Wejście: n (opcjonalnie inne parametry, np. stopień wypełnienia macierz).
Wyjście: zakodowana postać grafu o n wierzchołkach, takiego, że istnieje droga pomiędzy wierzchołkiem 1 a n. oraz, że nie istnieje połączenie bezpośrednie pomiędzy wierzchołkiem 1 a n. Postać taka powinna być akceptowalna przez funkcje z modułu 1.
Zbadania złożoności czasowej dla n=5:10 (dla wielu losowań (np. 100) ).
Wejście: zakres typu 5:10
Wyjście: tabela
Ilość wierzchołków | średni czas
5
6
…
10
Termin 4 listopada