Algorithmen I, SS 2015, gehalten am 17.06.2015, Vorlesung 18
45 minutes Posted Dec 7, 2015 at 4:20 pm.
Tiefensuche
Tiefensuchschema für G = (V,E)
DFS-Baum
Fertigstellungszeit
DFS-Nummerierung
Topologische Sortierung
Topologische Sortieren mittels DFS
Kap. 10: Kürzeste Wege
BFS – DFS
Anwendungen
Kantengewichte größer gleich Null
Dijkstras Algorithmus
Allgemeine Definitionen
Kante (u,v) relaxieren
Dijkstras Algorithmus: Pseudocode
Korrektheit
Implementierung?
Prioritätsliste
Implementierung BFS mit PQ statt FIFO
Beispiel
Dijkstra: Laufzeit
Laufzeit
Analyse im Mittel
Monotone ganzzahlige Prioritätslisten
Negative Kosten
Zurück zu Basiskonzepten (Abschnitt 10.1 im Buch)
Mehr Basiskonzepte
0:00
45:52
Show notes
18: Vorlesung |
Watch Video
