Dijkstra-Algorithmus

Kurz: Der Dijkstra-Algorithmus findet in einem Graphen mit nicht-negativen Kantengewichten den kürzesten Weg von einem Startknoten zu allen anderen.

Genauer: Er pflegt für jeden Knoten die bisher beste bekannte Entfernung. In jedem Schritt nimmt er den Knoten mit der kleinsten vorläufigen Entfernung, der noch nicht fertig ist, und prüft, ob die Wege zu seinen Nachbarn über ihn kürzer werden („Relaxation”).

Im Detail

• Datenstruktur: Mit einer Prioritätswarteschlange (Heap) erreicht er O((V + E) log V).
• Voraussetzung: Keine negativen Gewichte. Dafür gibt es Bellman-Ford.
• A*: Ergänzt Dijkstra um eine Schätzung der Restentfernung (Heuristik) und sucht so gezielter. Verbreitet in Spielen und Navigation.
• Anwendung: Routenplanung, Netzwerk-Routing (OSPF), Spielwegfindung.
• Beispiel: Knoten A–B (4), A–C (1), C–B (2): Der Weg A→C→B (3) ist kürzer als A→B (4).

Siehe auch: Breitensuche und Tiefensuche (BFS und DFS), Greedy-Algorithmen