Zaawansowane algorytmy i struktury danych/Ćwiczenia 6
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniaZadanie 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 drzewa najkrótszych ścieżek w czasie
, funkcję wagową , odległości z wybranego wierzchołka do w grafie , zaproponuj algorytm obliczania
Wskazówka