Dijkstra Algorithmus in Java

Der Dijkstra-Algorithmus ist ein fundamentaler Wegfindungsalgorithmus, der in Graphen verwendet wird, um den kürzesten Weg zwischen zwei Knoten zu finden. Dieser Beitrag bietet eine umfassende Erklärung des Dijkstra-Algorithmus sowie ein kommentiertes Java-Codebeispiel.

Der Dijkstra-Algorithmus: Eine Schritt-für-Schritt-Erklärung

1. Initialisierung:
   • Der Algorithmus beginnt mit der Initialisierung der Distanzen aller Knoten vom Startknoten aus. Die Distanz zum Startknoten selbst wird auf 0 gesetzt, während die Distanzen zu allen anderen Knoten auf unendlich (oder eine sehr große Zahl) gesetzt werden.
2. Prioritätswarteschlange:
   • Eine Prioritätswarteschlange wird verwendet, um die Knoten basierend auf ihren aktuellen Distanzen zu verwalten. Der Startknoten wird zuerst in die Warteschlange eingefügt.
3. Schleife:
   • In einer Schleife wird solange fortgefahren, bis die Prioritätswarteschlange leer ist. In jeder Iteration wird der Knoten mit der kürzesten aktuellen Distanz aus der Warteschlange entnommen.
4. Nachbarn überprüfen:
   • Für jeden Nachbarknoten des aktuellen Knotens werden die Distanzen aktualisiert. Wenn die Summe der aktuellen Distanz vom Startknoten zum aktuellen Knoten und der Kantenlänge zu einem Nachbarn kleiner ist als die aktuelle Distanz zum Nachbarn, wird die Distanz aktualisiert. Der Nachbarnode wird dann zur Prioritätswarteschlange hinzugefügt.
5. Wiederholung:
   • Dieser Prozess wird so lange wiederholt, bis alle Knoten besucht wurden oder bis die Distanzen nicht weiter verbessert werden können.

Beispielanwendung von Dijkstra auf einen Graphen

Angenommen, wir haben einen gerichteten Graphen mit Knoten A, B, C, D und E sowie gewichteten Kanten zwischen ihnen. Der Dijkstra-Algorithmus wird angewendet, um die kürzesten Distanzen von einem ausgewählten Startknoten (zum Beispiel A) zu allen anderen Knoten zu berechnen.

Die Ausgabe gibt dann die minimalen Distanzen von A zu allen anderen Knoten im Graphen an. Dies kann in vielen Anwendungen wie der Netzwerkroutingoptimierung oder der Verkehrsplanung nützlich sein.

Java-Codebeispiel von Dijkstra

import java.util.*;

public class DijkstraAlgorithm {

  // Dijkstra-Algorithmus zur Berechnung der kürzesten Wege in einem gewichteten
  // Graphen
  public static void dijkstra(Map<Node, Map<Node, Integer>> graph, Node start) {
    // Prioritätswarteschlange für die Auswahl des Knotens mit der geringsten
    // Distanz
    PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.getDistance()));
    start.setDistance(0);
    priorityQueue.add(start);

    // Haupt-Schleife des Dijkstra-Algorithmus
    while (!priorityQueue.isEmpty()) {
      Node current = priorityQueue.poll();

      // Iteration über alle Nachbarn des aktuellen Knotens
      for (Map.Entry<Node, Integer> neighborEntry : graph.get(current).entrySet()) {
        Node neighbor = neighborEntry.getKey();
        int newDistance = current.getDistance() + neighborEntry.getValue();

        // Aktualisierung der Distanz, falls ein kürzerer Weg gefunden wurde
        if (newDistance < neighbor.getDistance()) {
          priorityQueue.remove(neighbor);
          neighbor.setDistance(newDistance);
          priorityQueue.add(neighbor);
        }
      }
    }
  }

  // Hauptmethode zur Demonstration des Dijkstra-Algorithmus
  public static void main(String[] args) {
    // Erstellen des Graphen und der Knoten
    Map<Node, Map<Node, Integer>> graph = new HashMap<>();
    Node nodeA = new Node("A");
    Node nodeB = new Node("B");
    Node nodeC = new Node("C");
    Node nodeD = new Node("D");
    Node nodeE = new Node("E");

    // Hinzufügen der Kanten und Gewichte zum Graphen
    graph.put(nodeA, Map.of(nodeB, 1, nodeC, 4, nodeD, 2));
    graph.put(nodeB, Map.of(nodeA, 1, nodeC, 2, nodeE, 5));
    graph.put(nodeC, Map.of(nodeA, 4, nodeB, 2, nodeD, 1, nodeE, 3));
    graph.put(nodeD, Map.of(nodeA, 2, nodeC, 1, nodeE, 1));
    graph.put(nodeE, Map.of(nodeB, 5, nodeC, 3, nodeD, 1));

    // Anwendung des Dijkstra-Algorithmus
    dijkstra(graph, nodeA);

    // Ausgabe der kürzesten Distanzen vom Startknoten A zu allen anderen Knoten
    System.out.println("Kürzeste Distanzen vom Startknoten A:");
    for (Node node : graph.keySet()) {
      System.out.println(node.getName() + ": " + node.getDistance());
    }
  }
}

// Klasse zur Repräsentation eines Knotens im Graphen
class Node {
  private final String name;
  private int distance = Integer.MAX_VALUE; // Distanz des Knotens vom Startknoten

  // Konstruktor für die Initialisierung des Knotens mit einem Namen
  public Node(String name) {
    this.name = name;
  }

  // Getter-Methode für den Namen des Knotens
  public String getName() {
    return name;
  }

  // Getter-Methode für die Distanz des Knotens
  public int getDistance() {
    return distance;
  }

  // Setter-Methode für die Aktualisierung der Distanz des Knotens
  public void setDistance(int distance) {
    this.distance = distance;
  }
}

Fazit

Der Dijkstra-Algorithmus ist ein effizientes Verfahren zur Berechnung der kürzesten Wege in einem Graphen. Durch die Verwendung einer Prioritätswarteschlange und kontinuierliche Aktualisierung der Distanzen ermöglicht er die effiziente Ermittlung optimaler Wege in gewichteten Graphen.