Zaawansowane algorytmy i struktury danych/Ćwiczenia 6

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Pokaż, że iloczyn odległości jest przemienny względem dodawania, tzn. że dla macierzy , i rozmiaru zachodzi:



oraz


Wskazówka

Zadanie 2


Zaproponuj, jak wykorzystać algorytm Bellmana-Forda do sprawdzenia, czy w grafie i wagach krawędzi opisanych funkcją istnieje cykl o ujemnej wadze.

Rozwiązanie


Zadanie 3

Mając dane graf , funkcję wagową , odległości z wybranego wierzchołka do w grafie , zaproponuj algorytm obliczania drzewa najkrótszych ścieżek w czasie


Wskazówka