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

b) Algorytm Bellmana - Forda

  • 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:

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