StudySmarter: Besser Lernen
4.5 • +22k Bewertungen
Mehr als 22 Millionen Downloads
Kostenlos
|
|
Dijkstra Algorithmus

Du würdest gerne wissen, welches der kürzeste Weg zwischen München und Rotterdam ist? Welche Flüge Du buchen solltest, um möglichst günstig von Berlin nach Sydney zu fliegen? Über welche Leitungen sich Dein Computer mit dem Server von www.studysmarter.de verbinden soll?

Mockup Schule Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Dijkstra Algorithmus

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

Du würdest gerne wissen, welches der kürzeste Weg zwischen München und Rotterdam ist? Welche Flüge Du buchen solltest, um möglichst günstig von Berlin nach Sydney zu fliegen? Über welche Leitungen sich Dein Computer mit dem Server von www.studysmarter.de verbinden soll?

Dann könnte der Dijkstra Algorithmus für Dich hilfreich sein! Mit diesem Algorithmus kannst Du den kürzesten Weg von A nach B leicht bestimmen. Im Gegensatz zu anderen Greedy-Algorithmen berechnet der Dijkstra-Algorithmus jedoch immer die optimale Lösung.

Dijkstra Algorithmus Definition

1959 erfand der niederländische Mathematiker E. W. Dijkstra (ausgesprochen ˈdɛɪkˌstra) einen Algorithmus zum Finden kürzester Wege in gewichteten Graphen. Dieser Algorithmus ist mittlerweile in den meisten Routenplanern und Navigationsgeräten implementiert.

Dijkstras Algorithmus Erfinder Dijkstras Algorithmus Edsger Wybe StudySmarterAbb. 1 – Edsger Wybe Dijkstra

Bei seinem Verfahren werden zunächst alle kürzesten Wege eines Teils des gesamten Graphen bestimmt. Dann vergrößert man den Untergraphen schrittweise und untersucht die Auswirkung dieses Wachstums auf den kürzesten Weg.

Dijkstras Algorithmus basiert auf einer iterativen Erweiterung einer Menge von "billig" erreichbaren Knoten und kann daher als eine auf dem Greedy-Prinzip basierende Weiterentwicklung der Breitensuche für gewichtete Kanten aufgefasst werden.

Dijkstras Idee: Wenn der kürzeste Pfad von A nach C durch B verläuft, dann ist das Pfadsegment zwischen A und B die kürzeste Verbindung zwischen diesen beiden Knoten.

Ein kleiner Hinweis für Dich: Du kannst den Dijkstra-Algorithmus nur verwenden, um die kürzesten oder billigsten Wege zu berechnen, solange alle Kosten positiv sind. Treten auch negative Zahlen auf, funktioniert der Algorithmus nicht mehr.

Welche Schreibweise ist richtig: "Dijkstra-Algorithmus" oder "Dijkstra Algorithmus". In der Praxis werden beide Varianten eingesetzt.

Dijkstra Algorithmus Anwendung

Damit hast Du den Einstieg der Erklärung geschafft. Und jetzt siehst Du, welche Idee hinter dem Dijkstra Algorithmus steckt und wie er funktioniert.

Die Grundidee des Dijkstra Algorithmus ist folgende: Kanten im naiven Algorithmus geschickt wählen!

Dijkstra Algorithmus – Pseudocode

Wie kann der Pseudocode beim Dijkstra Algorithmus aussehen? Der Algorithmus von Dijkstra berechnet die Kosten des billigsten Pfads vom Startknoten zu allen anderen Knoten im Graph.

Der Dijkstra-Algorithmus wählt Schritt für Schritt den aktuell günstigsten Pfad aus, ausgehend vom Startknoten und durch die nächsten erreichbaren Knoten. Er kann auch Verbesserungen vornehmen. Dies wird so lange durchgeführt, bis alle Knoten besucht wurden und keine besseren Pfade gefunden werden.

Um den Dijkstra-Algorithmus auszuführen, benötigt man eine Warteschlange. Dort werden alle gefundenen Knoten eingefügt. An der Spitze dieser Warteschlange steht der Knoten, zu dem aktuell die günstigste Route vom Ursprungsknoten führt.

algorithm dijkstra(s) {

   input : Index s des Startknotens knoten[s]
   output : speichert für jeden Knoten die Distanz und den Vorgänger auf einem kürzesten Weg von s

// Initialisiere Attribute aller Knoten:

   for(i: 0 to n − 1) {
       setze distanz von knoten[i] auf ∞;
       setze vorgänger von knoten[i] auf null; 
   }

   setze distanz von knoten[s] auf 0; // Distanz des Startknotens zu sich selbst
   erzeuge PriorityQueue q mit allen Knoten;

// wende für den jeweils nächstgelegenen Knoten in q das Relaxationsprinzip an:

   while(q ist nicht leer) {
       u ← q.extractMin(); // entferne Knoten mit geringster Distanz
       for(w in Adjazenz von u) {
           d ← u.getDistanz() + gewicht[u.getIndex()][w.getIndex()];
           if (w.getDistanz() > d) { // Dreiecksungleichung verletzt?
               w.setDistanz(d); // setze Attribut distanz von w auf d
               w.setVorgänger(u); // setze Attribut vorgänger von w auf u
               q.decreaseKey(w,d); // sortiere Vorrangschlange mit neuer Distanz um
               }
           }
      }
 }

Am Ende des Dijkstra-Algorithmus kann dann der günstigste Pfad für jeden Knoten aufgebaut werden, indem die vorherigen Kanten durchlaufen werden, bis man den Startknoten erreicht. Wenn es vom Startknoten aus keinen Pfad zu einem Knoten gibt, bleiben seine Kosten unendlich, was bedeutet, dass der Knoten niemals erreichbar ist.

Wie der Algorithmus von Dijkstra funktioniert, siehst Du erneut an einem einfachen Beispiel. Aber bis dahin wartet noch etwas Java-Code auf Dich.

Dijkstra Algorithmus Java

Wie implementiert man Dijkstra Algorithmus am besten in Java? Im Folgenden steht für Dich ein möglicher Quellcode Schritt für Schritt erklärt.

/* implementiert den single source shortest path Algorithmus nach Dijkstra   
    
Es sind nur nicht-negative Kantenkosten zugelassen 
Verwendet wird eine Priority-Queue der Knoten, gewichtet mit den Kosten 
des vorläufig kürzesten Weges vom Startknoten bis zu diesem Knoten      */

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class DijkstraAlgo{

// Dijkstra Algorithmus

    public static void computePaths(Node source){
        source.shortestDistance=0;
       
// Implemetierung einer Prioritätswarteschlange

        PriorityQueue queue = new PriorityQueue();
        queue.add(source);

        while(!queue.isEmpty()){
            Node u = queue.poll();

// Besuche die Nachbarknoten, beginnend mit dem nächsten Knoten (kleinste shortestDistance)

            for(Edge e: u.adjacencies){
                Node v = e.target;
                double weight = e.weight;

                                    // relaxen(u,v,weight)

                double distanceFromU = u.shortestDistance+weight;
                if(distanceFromU < v.shortestDistance){

// Entferne v aus der Warteschlange, um den Wert für die kürzeste Entfernung zu aktualisieren

                    queue.remove(v);
                    v.shortestDistance = distanceFromU;
                    v.parent = u;
                    queue.add(v);
                    }
                }
            }
}

public static List getShortestPathTo(Node target){

// verfolge Pfad vom Ziel zur Start

    List path = new ArrayList();
    for(Node node = target; node!=null; node = node.parent){
        path.add(node);
        }

// Kehre die Reihenfolge um, sodass sie von der Start zum Ziel erfolgt

    Collections.reverse(path);
    return path;
}

public static void main(String[] args){

// Initialisiere den Basisgraphen auf der deutschen Karte

        Node n1 = new Node("München");
        Node n2 = new Node("Köln");
        Node n3 = new Node("Osnabrück");
        Node n4 = new Node("Augsburg");
        Node n5 = new Node("Frankfurt");
        Node n6 = new Node("Hannover");
        Node n7 = new Node("Paderborn");
        Node n8 = new Node("Thüngen");
        Node n9 = new Node("Leipzig");
        Node n10 = new Node("Münster");
        Node n11 = new Node("Dresden");
        Node n12 = new Node("Nürnberg");
        Node n13 = new Node("Rotterdam");
        Node n14 = new Node("Hamburg");

// Kanten initialisieren

        n1.adjacencies = new Edge[]{
            new Edge(n2,75),
            new Edge(n4,140),
            new Edge(n8,118)
        };


        n2.adjacencies = new Edge[]{
            new Edge(n1,75),
            new Edge(n3,71)
        };

        n3.adjacencies = new Edge[]{
            new Edge(n2,71),
            new Edge(n4,151)
        };

        n4.adjacencies = new Edge[]{
            new Edge(n1,140),
            new Edge(n5,99),
            new Edge(n3,151),
            new Edge(n6,80),
        };

        n5.adjacencies = new Edge[]{
            new Edge(n4,99),
            new Edge(n13,211)
        };

        n6.adjacencies = new Edge[]{
            new Edge(n4,80),
            new Edge(n7,97),
            new Edge(n12,146)
        };

        n7.adjacencies = new Edge[]{
            new Edge(n6,97),
            new Edge(n13,101),
            new Edge(n12,138)
        };

        n8.adjacencies = new Edge[]{
            new Edge(n1,118),
            new Edge(n9,111)
        };

        n9.adjacencies = new Edge[]{
            new Edge(n8,111),
            new Edge(n10,70)
        };

        n10.adjacencies = new Edge[]{
            new Edge(n9,70),
            new Edge(n11,75)
        };

        n11.adjacencies = new Edge[]{
            new Edge(n10,75),
            new Edge(n12,120)
        };

        n12.adjacencies = new Edge[]{
            new Edge(n11,120),
            new Edge(n6,146),
            new Edge(n7,138)
        };

        n13.adjacencies = new Edge[]{
            new Edge(n7,101),
            new Edge(n14,90),
            new Edge(n5,211)
        };

        n14.adjacencies = new Edge[]{
            new Edge(n13,90)
        };

        Node[] nodes = {n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14};

// Pfade berechnen

    computePaths(n1);


// kürzeste Wege ausgeben

    /*
        for(Node n: nodes){
            System.out.println("Distance to " + n + ": " + n.shortestDistance);
            List path = getShortestPathTo(n);
            System.out.println("Path: " + path);
        } */

    List path = getShortestPathTo(n13);
    System.out.println("Path: " + path);
    }
}

// Knoten definieren

class Node implements Comparable{
    public final String value;
    public Edge[] adjacencies;
    public double shortestDistance = Double.POSITIVE_INFINITY;
    public Node parent;
    public Node(String val){
    value = val;
    }
  
public String toString(){
    return value;
}

public int compareTo(Node other){
    return Double.compare(shortestDistance, other.shortestDistance);
    }
}

// Kanten definieren

class Edge{
    public final Node target;
    public final double weight;
    public Edge(Node targetNode, double weightVal){
        target = targetNode;
        weight = weightVal;
    }
}
Output: Path : [München, Augsburg, Hannover, Paderborn, Rotterdam]

Um das Programm verständlicher zu machen, kann man es in mehrere Klassen unterteilen:

  • Klasse Ausgabe(class main)
  • Klasse Dijkstra (class DijkstraAlgo)
  • Klasse Kanten(class Edge)
  • Klasse Knoten(class Node).

Die Dijkstra-Klasse ist die wichtigste Klasse in Programm. Es wird verwendet, um die kürzeste Entfernung zwischen dem Abfahrtsknoten(München) und dem Zielknoten(Rotterdam) zu berechnen. In Dijkstra werden Knoten und Prioritätswarteschlangenverwaltungslisten zuerst initialisiert, dann wird der Dijkstra-Algorithmus ausgeführt: Bei jeder Iteration wird das Element u in der Warteschlange mit einem Abstand zum Startknoten gesucht, der am kleinsten ist.

Neben der kürzesten Pfadlänge berechnet Dijkstra auch die Programmausführungszeit, indem die Systemzeit zu Beginn und nach der Ausführung des Algorithmus gemessen wird.

Der Zweck der Ausgabeklasse besteht darin, die kürzeste Entfernung zwischen dem Start- (München) und dem Zielknoten (Rotterdam), die zuvor vom Dijkstra-Algorithmus berechnet wurde, auf der Konsole auszugeben.

Dijkstra Algorithmus Beispiel

Hands-On Time! Jetzt kannst Du endlich loslegen. Der Algorithmus soll nun anhand eines Beispiels erklärt werden: Im folgenden Graphen ist der kürzeste Weg vom Knoten links zu dem ganz rechts gesucht.

In der nachfolgenden Tabelle findest Du den ganzen Algorithmus-Durchlauf des Beispielgraphen.

Dijkstra Algorithmus – Durchlauf

Dijkstra Algorithmus – Durchlauf

Die Funktionsweise des Dijkstra-Algorithmus wird am verständlichsten durch ein konkretes Beispiel.

Der Routenplaner und Dijkstra-Algorithmus

Stell Dir vor, Dein Routenplaner soll den schnellsten Weg von einem Ort a zu einem anderen Ort d ermitteln.

Die Verbindungen benachbarter Orte sind unten in einem kantengewichteten Graphen dargestellt:

Die Gewichte geben in diesem Kontext die Fahrzeit zwischen den Orten an. Die Gewichte sind also positiv.

Ein möglicher Weg von a nach d ist a ⇢ b ⇢ c ⇢ d mit der Fahrzeit 1 + 3 + 8= 12. Findest du einen schnelleren Weg?

Lösung:

Oft wird eine tabellarische Form verwendet, um die Ergebnisse der einzelnen Iterationen des Dijkstra-Algorithmus zusammenzufassen. Dies wird für das obige Beispiel in der folgenden Tabelle dargestellt.

Inhalt von Pentferntbesuchte KantenUpdate-Operationen
(a, 0)(a, 0)(a, b),(a, e)

(b, 1),(e, 7)

(b, 1),(e, 7)(b, 1) (b, c) (c, 4)
(c, 4),(e, 7) (c, 4) (c, d),(c, e),(c, f ) (d, 12),(f , 10)
(e, 7),(f , 10),(d, 12) (e, 7) (e, f ) (f , 8)
(f , 8),(d, 12) (f , 8) (f , c),(f , d) (d, 10)
(d, 10) (d, 10)

Das folgende Diagramm zeigt den konstruierten aufspannenden Baum, die Besuchsfolge der Knoten und die berechneten Abstände.

Der schnellste Weg von a nach d ist also a ⇢ e ⇢ f ⇢ d (7+1+3=11) mit der Fahrzeit 11.

Dijkstra Algorithmus Laufzeit

Die Kosten des Dijkstra-Algorithmus werden durch die Operationen zum Entfernen von Knoten und zum Anpassen der Abstandswerte benachbarter Knoten bestimmt. Wenn alle Operationen in der Prioritätswarteschlange in O(1) durchgeführt werden können, dann sind die Kosten für einen Graphen mit m Kanten und n Knoten O(m + n). Für eine Prioritätswarteschlange, die auf einer verketteten Liste basiert, wird dies zu O(n2) übersetzt.

In der folgenden Tabelle findest Du eine Übersicht über die zeitliche Komplexität des Dijkstra-Algorithmus in Abhängigkeit von der verwendeten Datenstruktur. Übrigens hat Dijkstra selbst den Algorithmus mit einem Array implementiert.

DatenstrukturTemTiTdkZeitkomplexitätallgemeinZeitkomplexitätfür m ∈ O(n)
ArrayO(n)O(1)O(1)O(n² + m) O(n²)
PriorityQueueO(log n) O(log n) O(n) O(n · log n + m · n) O(n²)
TreeSetO(log n) O(log n) O(log n) O(n · log n + m · log n) O(n · log n)
FibonacciHeapO(log n) O(1)O(1)O(n · log n + m) O(n · log n)
  1. Tem = TextractMinimum
  2. Ti = Tinsert
  3. Tdk = TdecreaseKey

Dijkstra Algorithmus Vorteile Nachteile

Was sind die größten Vorteile und Nachteile von Dijkstra Algorithmus? In der folgenden Tabelle findest Du die wichtigsten Vor- und Nachteile.

Vorteile des Dijkstra AlgorithmusNachteile des Dijkstra Algorithmus

Seine lineare Zeitkomplexität macht es einfach, den Algorithmus für große Probleme zu verwenden.

Kann nicht mit negativen Gewichten umgehen.

Der Algorithmus ist nützlich, um die kürzeste Entfernung zu finden, daher wird er auch in Google Maps und bei der Verkehrsberechnung verwendet.

Der größte Nachteil des Dijkstra-Verfahrens ist, dass der Graph nicht zielgerichtet durchsucht wird.

Kann man Dijkstras Algorithmus verbessern oder alle oben genannten Nachteile lösen? Die Antwort ist ganz simpel: Ja!

Es gibt eine Weiterentwicklung des Dijkstra-Algorithmus, der die Prüfung auf falsche Pfade mittels Heuristik vorzeitig beendet und deterministisch immer den kürzesten Pfad findet: der A*-Algorithmus.

Bei einem negativ gewichteten Graphen würdest Du stattdessen einen anderen Greedy-Algorithmus, wie den Bellman-Ford-Algorithmus verwenden.

Der Bellman-Ford-Algorithmus, benannt nach seinen Entwicklern Richard Bellman und Lester Ford, wird verwendet, um die kürzesten Wege in Graphen zu finden. Negative Gewichtskanten können eingeschlossen werden, aber es muss darauf geachtet werden, negative Gewichtszyklen von der Berücksichtigung auszuschließen.

Dijkstras Algorithmus - Das Wichtigste

  • Dijkstra Algorithmus Definition: Der Dijkstra-Algorithmus findet immer den kürzesten Weg von einem gegebenen Startknoten zu einem gegebenen Zielknoten, falls einer existiert und alle Kantengewichte nicht negativ sind.
  • Der Dijkstra-Algorithmus ist einer der Greedy-Algorithmen in der Graphentheorie.
  • Nachteil vom Dijkstra Algorithmus: Dijkstra Algorithmus erlaubt keine negativen Gewichte.
  • Dijkstra Algorithmus Laufzeit: T = Θ(V) · TExtractMin + Θ(E) · TDecreaseKey
  • Implementiere Q (Prioritätswarteschlange) als

    • Array: Laufzeit O(V2)

    • Binär-Heap: Laufzeit O(E · log(V))

    • Fibonacci-Heap: Laufzeit O(E + V · log(V))


Nachweise

  1. Abb. 1 - "File:EdsgerDijkstra.jpg" by Hamilton Richards is licensed under CC BY-SA 3.0.
  2. algorithms.discrete.ma.tum.de: Der Dijkstra-Algorithmus. (13.10.2022)
  3. fh-swf.de:Algorithmik. (13.10.2022)
  4. literateprograms.org: Dijksra's Algorithm. (Java)
  5. happycoders.eu: Dijkstra-Algorithmus. (13.10.2022)

Häufig gestellte Fragen zum Thema Dijkstra Algorithmus

Der Dijkstra-Algorithmus findet immer den kürzesten Weg von einem gegebenen Startknoten zu einem gegebenen Zielknoten.

Bei dem Verfahren werden zunächst alle kürzesten Wege eines Teils des gesamten Graphen bestimmt. Dann vergrößert man den Untergraphen schrittweise und untersucht die Auswirkung dieses Wachstums auf den kürzesten Weg. 

Im Gegensatz zu anderen Greedy-Algorithmen berechnet der Dijkstra-Algorithmus immer die optimale Lösung. 

Teste dein Wissen mit Multiple-Choice-Karteikarten

Wahr oder Falsch“Der Dijkstra Algorithmus dient der Findung des kürzesten Wegs innerhalb eines Graphen von einem Start- zu einem Endpunkt”

Wahr oder Falsch“Der Dijkstra Algorithmus wird beispielsweise in Routenplanern und Navigationsgeräten eingesetzt.”

Wahr oder Falsch“Der Dijkstra Algorithmus kann auch in Graphen mit negativen Kantengewichten angewendet werden.”

Weiter

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration

Entdecke Lernmaterial in der StudySmarter-App