Dijkstra-Algorithmus

Der Dijkstra-Algorithmus dient zur Bestimmung der kürzesten Wege von einem Knoten a zu allen anderen Knoten eines gerichteten Graphen G=(V,E). Es handelt sich daher um einen Baum-Algorithmus. Das Verfahren führt Iterationen durch.

Es benötigt für jeden Knoten i die Variablen Di und Ri zur Speicherung der (derzeit) kürzesten Entfernung und des Vorgängers im (derzeit) kürzesten Weg von a nach i sowie eine Menge MK markierter Knoten. Die Nachfolger eines Knotens i sind in der Menge Ni zusammengefasst. Der Algorithmus geht wie folgt vor: Start: Setze MK :={a}, D a := 0 sowie Di := für alle Knoten .

Iteration: Wiederhole 1. - 3. so lange, bis MK = 1. Wähle mit Dh = min { Di | } 2. Für jedes : Wenn Dj > Dh + chj , so setze Dj := Dh + chj; Rj := h; MK := 3. Setze MK := Wir wenden den Dijkstra-Algorithmus auf den Graphen an. Nach It. 1 gilt MK={2,4} und: It. 2: h = 4; keine Änderung für j = 2, D5 := 60; R5 := 4; MK = {2,5} It. 3: h = 2; D3 := 40; R3 := 2; MK = {3,5} It. 4: h = 3; D5 := 50; R5 := 3; MK = {5} It. 5: keine Änderungen; MK = Nach Abbruch des Verfahrens sind die kürzesten Entfernungen Di von a = 1 zu allen anderen Knoten i und die direkten Vorgänger Ri auf dem jeweils kürzesten Weg gespeichert: Aus den Ri lässt sich z.B. der kürzeste Weg von 1 nach 5 rekursiv, bei Knoten 5 beginnend, gemäß R5 = 3, R3 = 2 und R2= 1 zu (1, 2, 3, 5) bestimmen. Der Baum kürzester Wege ist durch fette Pfeile hervorgehoben.

Vorhergehender Fachbegriff: DIHZ | Nächster Fachbegriff: Diktatur

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Betriebsergebnis | Agrarkreditprogramm | Platzüberschreitender effektenverkehr

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer