Laboratorium 5

Algorytmy grafowe

     Ćwiczenie ma na celu zapoznanie się z dwoma rodzajami algorytmów: znajdującymi najkrótszą drogę w grafie skierowanym (digrafie) oraz tworzącymi najmniejsze drzewo rozpinające w grafie nieskierowanym. Badane będą następujące algorytmy:
Poszukiwanie najkrótszych dróg: Tworzenie najmniejszego drzewa rozpinającego: Dla wskazanych algorytmów należy określić doowiadczalnie zależność czasu obliczeń od liczby wierzchołków i krawędzi grafu. Wyniki należy porównać z szacunkami złożoności obliczeniowej przeprowadzonymi na podstawie analizy kodu. Wysoko punktowane będą również własne udoskonalenia kodu prowadzące do przyspieszenia działania algorytmów.

Uwagi

Do wykonania ćwiczenia niezbędna jest znajomość Przed przystąpieniem do ćwiczenia należy obowiązkowo zapoznać się z instrukcją do ćwiczenia i kodami źródłowymi. Przed przystąpieniem do pisania sprawozdania należy się zapoznać z informacjami_dodatkowymi.

Literatura

  • R. Sedgewick "Algorytmy w C++", Wydawnictwo RM, 1999.
  • R. Sedgewick, K. Wayne "Algorytmy", Wydawnictwo Helion, 2012.
  • A. Drozdek "C++ algorytmy i struktury danych", Wydawnictwo Helion, 2004.
  • M. Sysło, N. Deo, J. Kowalik "Algorytmy optymalizacji dyskretnej", PWN 1999.
    Instrukcja do ćwiczenia Źródła Materiały dodatkowe
    Wyślij sprawozdanie: