Glossar · approach
Dijkstra Algorithm
Polynomialer Algorithmus von Edsger Dijkstra (1959) für Single-Source-Shortest-Path auf Graphen mit nicht-negativen Kantengewichten; gierig — extrahiere den unbesuchten Knoten mit kleinster vorläufiger Distanz aus einer Prioritätswarteschlange und relaxiere seine Nachbarn; O((V+E) log V) mit Binary-Heap.
Dijkstra-AlgorithmusDijkstraDijkstras AlgorithmusDijkstra Shortest Path
Dijkstra-Algorithmus ist der polynomiale Algorithmus, den Edsger Dijkstra 1959 in einem zweiseitigen *Numerische Mathematik*-Papier definierte; er löst das Single-Source-Shortest-Path-Problem (kürzester Pfad von einem Quellknoten zu allen anderen Knoten) auf einem Graphen mit nicht-negativen Kantengewichten. Gieriger Ansatz: in jedem Schritt aus einer Prioritätswarteschlange den unbesuchten Knoten mit kleinster vorläufiger Distanz extrahieren und die Distanzen seiner Nachbarn relaxieren (aktualisieren). Komplexität: O((V+E) log V) mit Binary-Heap, O(E + V log V) mit Fibonacci-Heap. In der Single-Source-Single-Destination-Variante stoppt die Suche, sobald das Ziel erreicht ist; für Single-Source-All-Destinations wird der gesamte Graph verarbeitet. Grundlegend; eine Subroutine in zahllosen praktischen Systemen (Netzwerk-Routingprotokolle OSPF, Navigation, Distanz in sozialen Netzwerken, Paketvermittlung). A* (Hart-Nilsson-Raphael 1968) ist die heuristik-geführte Variante von Dijkstra; Contraction Hierarchies (Geisberger 2008) ist die moderne vorverarbeitungsbasierte Erweiterung für landesweite Straßennetze. Bei negativen Kanten ist Dijkstra nicht optimal — Bellman-Ford ist nötig. Cormen-Leiserson-Rivest-Stein (2009) *Introduction to Algorithms* ist die Lehrreferenz.
Örnek
In einem Field-Service-Betrieb wird der zeitkürzeste Pfad von Kunde 1 zu Kunde 12 auf dem städtischen Straßennetz-Graph in Millisekunden mit einem binary-heap-basierten Dijkstra berechnet; die Disposition identifiziert den nächstgelegenen Techniker zu einem eingehenden Notruf über eine Single-Source-All-Destinations-Dijkstra-Variante.