Motivation
Lektion 2 von 9 im Kurs Dijkstra-Algorithmus - Graph-Algorithmen von Coddy.
Dijkstra erweitert eine Menge von Knoten, deren kürzeste Entfernung bereits bekannt ist. Es schließt immer den nächstgelegenen, noch nicht abgeschlossenen Knoten ab und nutzt ihn dann, um die Entfernungen zu seinen Nachbarn zu verbessern (relaxieren).
Warum Dijkstra lernen?
- Überall: GPS-Routing, Netzwerk-Paket-Routing und jede Art von kostengünstigster Pfadfindung.
- Greedy, das funktioniert: ein klares Beispiel für eine gierige Auswahl, die nachweislich das Optimum liefert, solange die Gewichte nicht negativ sind.
- Grundlage: Seine Relaxations-Idee taucht in A* und anderen Algorithmen für kürzeste Pfade wieder auf.
Wichtig: Dijkstra setzt voraus, dass es keine negativen Gewichte gibt. Negative Kanten erfordern Bellman-Ford, den nächsten Kurs.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
