20: Algorithmen I, Vorlesung, SS 2019, 15.07.2019 Algorithmen 1, SS2019, Vorlesung

20 |
0:00:00 Start
0:01:21 Kürzeste Wege: Definition
0:02:23 Dijkstras Algorithmus. Pseudocode
0:08:12 Dijkstra: negative Kantengewichte
0:17:02 Monotone ganzzahlige Prioritätslisten
0:19:49 Negative Zyklen
0:21:55 Zurück zu Basiskonzepten
0:26:31 Allgemeines Korrektheitskriterium
0:31:09 Bellman-Ford-Algorithmus
0:39:29 Beispiel
0:43:57 Bellman-Ford: Laufzeit
0:45:30 Azyklische Graphen
0:49:38 Von überall nach überall
0:52:15 Kürzeste Wege: Zusammenfassung
0:57:10 Exkurs: Routing in Straßennetzwerken
1:01:56 Ideen für Routenplanung
1:03:47 Ansatz: Transit-Node Routing
1:09:15 Zweite Beobachtung
1:17:04 Offene Fragen
1:18:36 Minimale Spannbäume (MST)
1:23:59 Minimal aufspannende Wälder (MSF)