Algorytm Floyda-Warshalla (projekt)
Spis treści
Wariant podstawowy (na ocenę 3,5)
Należy zaimplementować algorytm Floyda-Warshalla w wersji obliczającej odległości pomiędzy każdą parą wierzchołków w grafie ważonym.
Dodatkowo należy opanować (ze zrozumieniem) teorię dotyczącą tego algorytmu: zasadę działania, złożoność obliczeniową czasową i pamięciową, a także zrozumieć ideę programowania dynamicznego.
Ocena może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.
Rozszerzenie (na ocenę 5)
Algorytm oprócz odległości powinien znaleźć także same ścieżki. Sam program powinien wypisywać ścieżki pomiędzy wskazanymi wierzchołkami.
Przykładowe pytania sprawdzające
- Jak działa algorytm Floyda-Warshalla? Co zawiera używana przez niego macierz odległości po k-tej iteracji? Jak ta macierz jest wypełniana?
- (w przypadku wersji algorytmu szukającego także samych ścieżek) Co zawiera dodatkowa macierz umożliwiająca odtwarzanie ścieżek? Jak jest ona wypełniana? Jak działa algorytm wypisujący na jej podstawie ścieżki?
- Jaka jest złożoność czasowa algorytmu Floyda-Warshalla? Wskazać miejsca w kodzie (pętle, rekurencje), które za to opowiadają.
- Jaka jest złożoność pamięciowa algorytmu Floyda-Warshalla? Wskazać miejsca w kodzie gdzie alokowana jest pamięć (w jakiej ilości?).
- Algorytm Floyda-Warshalla jest przykładem algorytmu dynamicznego. Co to jest programowanie dynamiczne? Na jakiej zasadzie ono działa i jakie daje korzyści?