04: Algorithmen II, Vorlesung und Übung, WS 2018/19, 23.10.2018

04 | 0:00:00 Start 0:00:04 Dijkstra's Algorithmus: Pseudocode 0:00:39 Laufzeit 0:01:30 Laufzeit im Durchschnitt 0:02:05 Lineare Laufzeit fur dichte Graphen 0:02:21 Satz 1 0:11:50 Prafixminima einer Zufallsfolge 0:14:11 Monotone ganzzahlige Prioritatslisten 0:17:38 Bucket-Queue 0:20:18 Operationen 0:24:46 Laufzeit Dijkstra mit Bucket-Queues 0:26:07 Radix-Heaps 0:29:28 Definition 0:32:05 Radix-Heap_invariante 0:36:38 Radix Heap: deleteMin 0:39:34 Buckets 0:41:40 Lufzwit Dijkstra mit Radix-Heaps 0:42:31 Ubung 0:42:36 Amortisierte Analyse 0:52:53 Legende 0:54:44 Fibonacci Heaps - Insert 0:56:45 Fibonacci Heaps - Delete Min 1:08:31 Fibonacci Heaps - Decrease Key