Back خوارزمية ديكسترا Arabic Алгоритъм на Дейкстра Bulgarian Dijkstrin algoritam BS Algorisme de Dijkstra Catalan Dijkstrův algoritmus Czech Algorithm Dijkstra Welsh Dijkstras algoritme Danish Αλγόριθμος του Ντάικστρα Greek Dijkstra's algorithm English Algoritmo de Dijkstra Spanish
Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen[1] und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem der (oder allen) übrigen Knoten in einem kantengewichteten Graphen (sofern dieser keine Negativkanten enthält).
Für unzusammenhängende ungerichtete Graphen ist der Abstand zu denjenigen Knoten unendlich, zu denen kein Pfad vom Startknoten aus existiert. Dasselbe gilt auch für gerichtete nicht stark zusammenhängende Graphen. Dabei wird der Abstand synonym auch als Entfernung, Kosten oder Gewicht bezeichnet.
- ↑ Tobias Häberlein: Praktische Algorithmik mit Python. Oldenbourg, München 2012, ISBN 978-3-486-71390-9, S. 162 ff.