KIT | KIT-Bibliothek | Impressum | Datenschutz

Algorithmen II, Vorlesung und Übung, WS 2016/17, 26.10.2016, 04

Schulz, Christian; Axtmann, Michael; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:10 Vorlesung: Fortgeschrittene Graphenalgorithmen, 3 Kürzeste Wege
  • 0:01:16 Wiederholung
  • 0:12:21 Definition msd (a,b)
  • 0:13:08 Radix Heap: deleteMin
  • 0:13:51 Bucket B(i) bei Änderung von min
  • 0:15:01 All-Pairs Shortest Paths
  • 0:16:15 Algorithmen Brutal – Belman-Ford-Algorithmus für beliebige Kantengewichte
  • 0:18:32 Knotenpotenziale
  • 0:25:00 Wie berechnen wir Potenziale?
  • 0:31:44 Algorithmus
  • 0:33:16 Laufzeit
  • 0:34:36 Hilfsknoten
  • 0:35:25 Distanz zu einem Zielknoten t
  • 0:37:24 Ideen für Routenplanung
  • 0:38:22 Bidirektionale Suche
  • 0:39:50 A-Suche
  • 0:42:52 Benötige Eigenschaften von f(v)
  • 0:44:59 Wie finden wir f(v)?
  • 0:46:01 Landmarks
  • 0:46:44 Zusammenfassung Kürzeste Wege
  • 0:47:32 Übung: Inhalt
  • 0:48:31 KaHIP: Implementierung einer BFS
  • 0:56:22 Spezielle Priority Queues
  • 0:58:25 Bucket Queues
  • 1:02:36 Radix Heaps
  • 1:24:08 Average case Analyse für MST


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 10.11.2016
Erstellungsdatum 26.10.2016
DOI 10.5445/DIVA/2016-703
Identifikator KITopen-ID: 1000117356
Serie Algorithmen II, Vorlesung, WS 2016/17
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page