18: Algorithmen I, Vorlesung und Übung, SS 2016, am 22.06.2016
1 hour Posted Jun 28, 2016 at 7:52 am.
Starten
Erinnerung VL 20.06.2016
Erinnerung: analoger Algorithmus
Dijkstra: Implementierung?
Prioritätsliste
Implementierung ≈ BFS mit PQ statt FIFO
Beispiel
Dijkstra: Laufzeit
Analyse im Mittel
Monotone ganzzahlige Prioritätslisten
Negative Kosten
Beginn Übung 9
Roadmap
Organisatorisches
Aufgabe 3
Breitensuche (Wie war das nochmal...)
Breitensuche für nicht zusammenhängende, ungerichtete Graphen
Breitensuche in DAGs für nicht zusammenhängende Graphen
Dijkstras Algorithmus
Bidirektionale Suche
Bidirektionale Suche Definitionen
Bidirektionale Suche Vorgehen
Pingo! Was sind gute Abbruchstrategien?
Abbruchstrategie (1)
Abbruchstrategie (2)
Beispiel
Bemerkungen
Graph-Datenstruktur
Pingo! Wie schnell wird eine Routing-Anfrage?
Speedup Techniques
Mehr davon?
0:00
1:00:22
Show notes
18 |
Watch Video
