Empfehlungen
A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z  
  Home Top 10 Fachbereiche News Hilfe & FAQ
 

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

   Beliebte Artikel

Bestimmte Erklärungen und Begriffsdefinitionen erfreuen sich bei unseren Lesern ganz besonderer Beliebtheit. Diese werden mehrmals pro Jahr aktualisiert.

  Cash Flow

  Bausparen

  Fremdwährungskonto


     © 2023-2024 Wirtschaftslexikon24.com       All rights reserved.      Home  |  Datenschutzbestimmungen  |  Impressum  |  Rechtliche Hinweise
Aktuelles Wirtschaftslexikon