Dijkstra Algorithmus

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.

Abb. 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.

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.

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.

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.

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

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(n²) ü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.

1. T_em = T_{extractMinimum}
2. T_i = T_insert
3. T_dk = T_decreaseKey

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.

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.