Lexikon der Mathematik: Dijkstra, Algorithmus von
liefert in einem zusammenhängenden und bewerteten Graphen G mit einer Bewertung ϱ(k) > 0 für jede Kante k ∈ K(G) die kürzesten Wege von einer festen Ecke u ∈ E(G) aus zu allen übrigen Ecken des Graphen.
Dieser schöne und einfache Algorithmus von Dijkstra aus dem Jahre 1959 wurde zur gleichen Zeit unabhängig auch von Dantzig entdeckt. Er läßt sich wie folgt beschreiben.
Man bestimme zunächst eine Ecke y1, die der Ecke u am nächsten ist. Wegen ϱ(k) > 0 ist y1 natürlich eine zu u adjazente Ecke. Im zweiten Schritt bestimme man eine Ecke y2, die der Ecke u am zweitnächsten ist. Eine solche Ecke ist dann adjazent zu u oder y1. Im dritten Schritt bestimme man eine Ecke y3, die der Ecke u am drittnächsten ist. Die Ecke y3 ist dann adjazent zu u, y1 oder y2, usw.
Dieser Algorithmus, der für gerichtete Graphen mit positiver Bewertung völlig analog verläuft, besitzt die Komplexität O(|E(G)|2).
Schreiben Sie uns!