Direkt zum Inhalt

Lexikon der Mathematik: Dijkstra, Algorithmus von

liefert in einem zusammenhängenden und bewerteten Graphen G mit einer Bewertung ϱ(k) > 0 für jede Kante kK(G) die kürzesten Wege von einer festen Ecke uE(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!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.