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?

Dijkstra Algorithmus Dijkstra Algorithmus

Erstelle Lernmaterialien über Dijkstra Algorithmus mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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

    Welches Problem löst der Dijkstra Algorithmus? 

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

    Wie funktioniert der Dijkstra Algorithmus? 

    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. 

    Ist Dijkstra optimal? 

    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
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Dijkstra Algorithmus Lehrer

    • 12 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

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

    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!