Dijkstra-Algorithmus für kürzeste Wege in Java

1. Übersicht

Der Schwerpunkt in diesem Artikel liegt auf dem Problem des kürzesten Pfades (SPP), einem der grundlegenden theoretischen Probleme, die in der Graphentheorie bekannt sind, und wie der Dijkstra-Algorithmus verwendet werden kann, um es zu lösen.

Das grundlegende Ziel des Algorithmus besteht darin, den kürzesten Weg zwischen einem Startknoten und dem Rest des Graphen zu bestimmen.

2. Problem mit dem kürzesten Weg mit Dijkstra

Bei einem positiv gewichteten Diagramm und einem Startknoten (A) bestimmt Dijkstra den kürzesten Weg und die kürzeste Entfernung von der Quelle zu allen Zielen im Diagramm:

Die Kernidee des Dijkstra-Algorithmus besteht darin, kontinuierlich längere Pfade zwischen dem Startknoten und allen möglichen Zielen zu eliminieren.

Um den Prozess im Auge zu behalten, benötigen wir zwei unterschiedliche Knotensätze, die festgelegt und nicht abgewickelt sind.

Abgerechnete Knoten sind solche mit einem bekannten Mindestabstand von der Quelle. Die Menge der ungeklärten Knoten sammelt Knoten, die wir von der Quelle aus erreichen können, aber wir kennen nicht den Mindestabstand vom Startknoten.

Hier ist eine Liste der Schritte, die Sie ausführen müssen, um das SPP mit Dijkstra zu lösen:

  • Setzen Sie den Abstand zu startNode auf Null.
  • Stellen Sie alle anderen Abstände auf einen unendlichen Wert ein.
  • Wir fügen den startNode zu den nicht veränderten Knoten hinzu.
  • Während der Satz der ungeklärten Knoten nicht leer ist, haben wir:
    • Wählen Sie einen Bewertungsknoten aus dem Satz nicht abgewickelter Knoten aus. Der Bewertungsknoten sollte derjenige mit dem geringsten Abstand von der Quelle sein.
    • Berechnen Sie neue Entfernungen zu direkten Nachbarn, indem Sie bei jeder Bewertung den niedrigsten Abstand einhalten.
    • Fügen Sie Nachbarn zu den noch nicht festgelegten Knoten hinzu, die noch nicht festgelegt sind.

Diese Schritte können in zwei Phasen zusammengefasst werden: Initialisierung und Bewertung. Mal sehen, wie sich das auf unser Beispieldiagramm auswirkt:

2.1. Initialisierung

Bevor wir alle Pfade im Diagramm untersuchen, müssen wir zunächst alle Knoten mit einer unendlichen Entfernung und einem unbekannten Vorgänger mit Ausnahme der Quelle initialisieren.

Als Teil des Initialisierungsprozesses müssen wir Knoten A den Wert 0 zuweisen (wir wissen, dass der Abstand von Knoten A zu Knoten A offensichtlich 0 ist).

Daher wird jeder Knoten im Rest des Diagramms mit einem Vorgänger und einer Entfernung unterschieden:

Um den Initialisierungsprozess abzuschließen, müssen wir Knoten A zu den ungeklärten Knoten hinzufügen, die so eingestellt sind, dass sie zuerst im Bewertungsschritt ausgewählt werden. Beachten Sie, dass der festgelegte Knotensatz noch leer ist.

2.2. Auswertung

Nachdem wir unser Diagramm initialisiert haben, wählen wir den Knoten mit dem geringsten Abstand von der ungeklärten Menge aus und bewerten dann alle benachbarten Knoten, die sich nicht in festgelegten Knoten befinden:

Die Idee ist, das Kantengewicht zur Entfernung des Bewertungsknotens hinzuzufügen und es dann mit der Entfernung des Ziels zu vergleichen. zB für Knoten B ist 0 + 10 niedriger als INFINITY, daher beträgt der neue Abstand für Knoten B 10 und der neue Vorgänger A, dasselbe gilt für Knoten C.

Knoten A wird dann von den nicht festgelegten Knoten zu den festgelegten Knoten verschoben.

Die Knoten B und C werden zu den ungeklärten Knoten hinzugefügt, da sie erreichbar sind, aber ausgewertet werden müssen.

Nachdem wir nun zwei Knoten in der ungeklärten Menge haben, wählen wir den Knoten mit dem niedrigsten Abstand (Knoten B) und wiederholen ihn, bis wir alle Knoten im Diagramm festgelegt haben:

In der folgenden Tabelle sind die Iterationen zusammengefasst, die während der Bewertungsschritte ausgeführt wurden:

Wiederholung Unruhig Erledigt EvaluationNode EIN B. C. D. E. F.
1 EIN - - EIN 0 A-10 A-15 X-∞ X-∞ X-∞
2 B, C. EIN B. 0 A-10 A-15 B-22 X-∞ B-25
3 C, F, D. A, B. C. 0 A-10 A-15 B-22 C-25 B-25
4 D, E, F. A, B, C. D. 0 A-10 A-15 B-22 D-24 D-23
5 E, F. A B C D F. 0 A-10 A-15 B-22 D-24 D-23
6 E. A, B, C, D, F. E. 0 A-10 A-15 B-22 D-24 D-23
Finale - - ALLE KEINER 0 A-10 A-15 B-22 D-24 D-23

Die Notation B-22 bedeutet beispielsweise, dass Knoten B der unmittelbare Vorgänger ist, mit einem Gesamtabstand von 22 von Knoten A.

Schließlich können wir die kürzesten Wege von Knoten A wie folgt berechnen:

  • Knoten B: A -> B (Gesamtabstand = 10)
  • Knoten C: A -> C (Gesamtabstand = 15)
  • Knoten D: A -> B -> D (Gesamtabstand = 22)
  • Knoten E: A -> B -> D -> E (Gesamtentfernung = 24)
  • Knoten F: A -> B -> D -> F (Gesamtabstand = 23)

3. Java-Implementierung

In dieser einfachen Implementierung stellen wir einen Graphen als eine Reihe von Knoten dar:

public class Graph { private Set nodes = new HashSet(); public void addNode(Node nodeA) { nodes.add(nodeA); } // getters and setters }

A node can be described with a name, a LinkedList in reference to the shortestPath, a distance from the source, and an adjacency list named adjacentNodes:

public class Node { private String name; private List shortestPath = new LinkedList(); private Integer distance = Integer.MAX_VALUE; Map adjacentNodes = new HashMap(); public void addDestination(Node destination, int distance) { adjacentNodes.put(destination, distance); } public Node(String name) { this.name = name; } // getters and setters }

The adjacentNodes attribute is used to associate immediate neighbors with edge length. This is a simplified implementation of an adjacency list, which is more suitable for the Dijkstra algorithm than the adjacency matrix.

As for the shortestPath attribute, it is a list of nodes that describes the shortest path calculated from the starting node.

By default, all node distances are initialized with Integer.MAX_VALUE to simulate an infinite distance as described in the initialization step.

Now, let's implement the Dijkstra algorithm:

public static Graph calculateShortestPathFromSource(Graph graph, Node source) { source.setDistance(0); Set settledNodes = new HashSet(); Set unsettledNodes = new HashSet(); unsettledNodes.add(source); while (unsettledNodes.size() != 0) { Node currentNode = getLowestDistanceNode(unsettledNodes); unsettledNodes.remove(currentNode); for (Entry  adjacencyPair: currentNode.getAdjacentNodes().entrySet()) { Node adjacentNode = adjacencyPair.getKey(); Integer edgeWeight = adjacencyPair.getValue(); if (!settledNodes.contains(adjacentNode)) { calculateMinimumDistance(adjacentNode, edgeWeight, currentNode); unsettledNodes.add(adjacentNode); } } settledNodes.add(currentNode); } return graph; }

The getLowestDistanceNode() method, returns the node with the lowest distance from the unsettled nodes set, while the calculateMinimumDistance() method compares the actual distance with the newly calculated one while following the newly explored path:

private static Node getLowestDistanceNode(Set  unsettledNodes) { Node lowestDistanceNode = null; int lowestDistance = Integer.MAX_VALUE; for (Node node: unsettledNodes) { int nodeDistance = node.getDistance(); if (nodeDistance < lowestDistance) { lowestDistance = nodeDistance; lowestDistanceNode = node; } } return lowestDistanceNode; }
private static void CalculateMinimumDistance(Node evaluationNode, Integer edgeWeigh, Node sourceNode) { Integer sourceDistance = sourceNode.getDistance(); if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) { evaluationNode.setDistance(sourceDistance + edgeWeigh); LinkedList shortestPath = new LinkedList(sourceNode.getShortestPath()); shortestPath.add(sourceNode); evaluationNode.setShortestPath(shortestPath); } }

Now that all the necessary pieces are in place, let's apply the Dijkstra algorithm on the sample graph being the subject of the article:

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"); Node nodeF = new Node("F"); nodeA.addDestination(nodeB, 10); nodeA.addDestination(nodeC, 15); nodeB.addDestination(nodeD, 12); nodeB.addDestination(nodeF, 15); nodeC.addDestination(nodeE, 10); nodeD.addDestination(nodeE, 2); nodeD.addDestination(nodeF, 1); nodeF.addDestination(nodeE, 5); Graph graph = new Graph(); graph.addNode(nodeA); graph.addNode(nodeB); graph.addNode(nodeC); graph.addNode(nodeD); graph.addNode(nodeE); graph.addNode(nodeF); graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA); 

Nach der Berechnung werden die Attribute kürzester Pfad und Abstand für jeden Knoten im Diagramm festgelegt. Wir können sie durchlaufen, um zu überprüfen, ob die Ergebnisse genau mit denen übereinstimmen, die im vorherigen Abschnitt gefunden wurden.

4. Fazit

In diesem Artikel haben wir gesehen, wie der Dijkstra-Algorithmus das SPP löst und wie es in Java implementiert wird.

Die Implementierung dieses einfachen Projekts finden Sie unter dem folgenden GitHub-Projektlink.