KIT | KIT-Bibliothek | Impressum | Datenschutz

Algorithmen I, SS 2015, gehalten am 24.06.2015, Vorlesung 20

Meyerhenke, Henning

  • 00:00:07 Algorithmen brutal – Bellmann-Ford-Algorithmus für beliebige Kantengewichte
  • 00:00:17 Allgemeines Korrektheitskriterium
  • 00:00:49 Zyklische Graphen (10.2 im Buch)
  • 00:01:01 Von überall nach überall
  • 00:01:16 Kürzeste Wege: Zusammenfassung
  • 00:01:20 Straßennetzwerke
  • 00:01:21 Ideen für Routenplanung
  • 00:02:01 Beispiel
  • 00:02:06 Transit-Node Routing
  • 00:02:40 Kap. 11: Minimale Spannbäume
  • 00:03:01 Minimale Spannbäume (MST)
  • 00:03:06 Minimale spannende Wälder (MSF)
  • 00:03:07 Anwendungen
  • 00:03:19 MST-Kanten auswählen und verwerfen
  • 00:05:55 Der Jarnik-Prim-Algorithmus
  • 00:18:18 Analyse
  • 00:23:38 Kruskals Algorithmus (1956)
  • 00:27:05 Kruskals Algorithmus – Korrektheit
  • 00:28:08 Union-Find Datenstruktur
  • 00:31:53 Union-Find Datenstruktur – Erste Version
  • 00:36:33 Pfadkompression
  • 00:39:00 Union by Rank
  • 00:40:43 Analyse – nur Union by rank
  • 00:45:11 Analyse – Pfadkompression + Union by rank
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 08.12.2015
Erstellungsdatum 24.06.2015
DOI 10.5445/DIVA/2015-934
Identifikator KITopen-ID: 1000113571
Serie 20
Serie Algorithmen 1, Vorlesung und Übung, SS 2015
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page