MOKIP 3.10.2012 (grupa zaawansowana)
Najkrótsze ścieżki w grafach.
1. Nawiązanie do poprzednich zajęć z dnia 26 X 2012r.
- problem rozspójniania się grafu wraz z usuwaniem poszczególnych krawędzi
- trik z odwracaniem czasu, zastosowanie struktury Find & Union
- zadanie Małpki X OI
2. Najkrótsze ścieżki w grafie nie-/ skierowanym bez wag wyznaczamy BFS-em.
3. Wyznaczanie najkrótszych ścieżek w grafie ważonym z jednego źródła do pozostałych wierzchołków:
a) Algorytm Dijkstry
- tylko nieujemne wagi krawędzi
- pseudokod O(E*logV)
- zastosowanie kopca typu min. dla kolejki priorytetowej
- zadanie Dostawca
- także dla ujemnych wag krawędzi (wykrywa ujemne cykle)
- pseudokod O(V^2)
4. Wyznaczanie najkrótszych ścieżek w grafie ważonym pomiędzy wszystkimi parami wierzchołków:
- algorytm Floyda - Warshalla
- psudokod O(V^3)
5. Podchwytliwe zadanie Godzilla ONTAK 2010:
- nie trzeba wczytywać struktury grafu
- maks. ilość ofiar jest stała dla podanych wierzowców (można opisać wzorem)
6. Ciekawe zadanie Restauracje .
- Aby rozwiązać problem należy odpalić Algorytm Dijkstry ustawiając odległości wyróżnionych wieszchołków na 0.
7. Paczka kodów z wykładu, a w niej:
- Algorytm Dijkstry (jako rozwiązanie zadania Dostawca)
- Algorytm Bellmana-Forda
- Algorytm Floyda-Warshalla
- Małpki z X OI (2 rozwiązania, oryginalne podane na kółku i alternatywne z użyciem drugiego Find&Union)
- Restauracje z PA 2001
- Godzilla z ONTAK 2010
wersja strony: 12, ostatnia edycja: 13 Oct 2012 09:40