Wykład 13. Proste (czyżby?) algorytmy grafowe

Na wykładzie omówiłem różne w sumie podstawowe algorytmy związane z grafami. Przy większości z nich wspomniałem o tym, jak według mojego doświadczenia najlepiej (np. najłatwiej) go zaimplementować, jak najłatwiej uzasadnić jego poprawność i jak go stosować do różnych fajnych rzeczy. Na wykładzie zakładałem raptem... znajomość poniższych algorytmów:).

  • BFS (tak, nawet w zwykłym BFS-ie coś ciekawego siedzi!).
  • Silnie spójne składowe i sortowania topologiczne.
  • Cykl Eulera.
  • Algorytm Dijkstry z moim ulubionym zastosowaniem.
  • Algorytm Floyda-Warshalla i zastosowania do ujemnych cykli w grafie (patrz zadanie Studia z PA 2008).
  • "Dzielenie przez 32" na przykładzie algorytmów grafowych (w tym zliczanie trójkątów w grafie i inne Floydy).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3130. Termin: 24.02.2009, 16:00-17:45.

Dostępne materiały: Nagrania.