Algorytm Floyda-Warshalla (projekt)

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?