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

Autor

Christian Schulz, Michael Axtmann

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

04 |
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

Laufzeit (hh:mm:ss)

01:32:08

Serie

Algorithmen II, Vorlesung, WS 2016/17

Publiziert am

10.11.2016

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz