KIT | KIT-Bibliothek | Impressum | Datenschutz

Algorithmen I, SS 2015, gehalten am 22.06.2015, Vorlesung 19

Meyerhenke, Henning

  • 00:00:07 Dijkstra: Laufzeit
  • 00:02:21 Laufzeit
  • 00:03:55 Negative Kosten
  • 00:04:43 Allgemeines Korrektheitskriterium
  • 00:09:44 Algorithmen brutal – Bellmann-Ford-Algorithmus für beliebige Kantengewichte
  • 00:11:00 Allgemeines Korrektheitskriterium
  • 00:12:16 Negative Kreise finden
  • 00:14:35 Beispiel
  • 00:18:37 Bellmann-Ford – Laufzeit
  • 00:18:57 Laufzeit
  • 00:19:53 Zyklische Graphen (10.2 im Buch)
  • 00:22:04 Von überall nach überall
  • 00:24:40 Kürzeste Wege: Zusammenfassung
  • 00:25:56 Mehr zu kürzesten Wegen
  • 00:28:01 Exkurs: Routing in Straßennetzwerken
  • 00:29:58 Straßennetzwerke
  • 00:30:57 Distanz zu einem Zielknoten t
  • 00:32:58 Ideen für Routenplanung
  • 00:40:00 Straßennetzwerke
  • 00:43:10 Approach: Transit-Node Routing
  • 00:44:09 Beispiel
  • 00:46:48 Erste Beobachtung
  • 00:48:04 Zweite Beobachtung
  • 00:48:25 Transit-Node Routing
  • 00:52:41 Beispiel: Transitknoten
  • 00:53:54 Experimente
  • 00:58:20 Offene Fragen
  • 00:58:58 Kap. 11: Minimale Spannbäume
  • 01:00:18 Minimale Spannbäume (MST)
  • 01:02:26 Minimale spannende Wälder (MSF)
  • 01:03:11 Anwendungen
  • 01:09:31 MST-Kanten auswählen und verwerfen
  • 01:15:58 Der Jarnik-Prim-Algorithmus
Open Access Logo


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