Algorithme Dijkstra Shortest Path en Java

1. Vue d'ensemble

Cet article met l'accent sur le problème du chemin le plus court (SPP), qui est l'un des problèmes théoriques fondamentaux connus en théorie des graphes, et comment l'algorithme de Dijkstra peut être utilisé pour le résoudre.

L'objectif de base de l'algorithme est de déterminer le chemin le plus court entre un nœud de départ et le reste du graphique.

2. Problème de chemin le plus court avec Dijkstra

Étant donné un graphique pondéré positivement et un nœud de départ (A), Dijkstra détermine le chemin le plus court et la distance entre la source et toutes les destinations du graphique:

L'idée centrale de l'algorithme de Dijkstra est d'éliminer continuellement les chemins plus longs entre le nœud de départ et toutes les destinations possibles.

Pour suivre le processus, nous avons besoin de deux ensembles distincts de nœuds, installés et non installés.

Les nœuds établis sont ceux dont la distance minimale connue de la source est connue. L'ensemble de nœuds non réglés rassemble les nœuds que nous pouvons atteindre depuis la source, mais nous ne connaissons pas la distance minimale par rapport au nœud de départ.

Voici une liste d'étapes à suivre pour résoudre le SPP avec Dijkstra:

  • Définissez la distance de startNode sur zéro.
  • Définissez toutes les autres distances sur une valeur infinie.
  • Nous ajoutons le startNode à l'ensemble de nœuds non définis.
  • Bien que l'ensemble de nœuds non réglés ne soit pas vide, nous:
    • Choisissez un nœud d'évaluation dans l'ensemble de nœuds non définis, le nœud d'évaluation doit être celui avec la distance la plus faible de la source.
    • Calculez de nouvelles distances aux voisins directs en gardant la distance la plus basse à chaque évaluation.
    • Ajoutez des voisins qui ne sont pas encore installés à l'ensemble de nœuds non définis.

Ces étapes peuvent être regroupées en deux étapes, l'initialisation et l'évaluation. Voyons comment cela s'applique à notre exemple de graphique:

2.1. Initialisation

Avant de commencer à explorer tous les chemins du graphe, nous devons d'abord initialiser tous les nœuds avec une distance infinie et un prédécesseur inconnu, à l'exception de la source.

Dans le cadre du processus d'initialisation, nous devons attribuer la valeur 0 au nœud A (nous savons que la distance du nœud A au nœud A est évidemment 0)

Ainsi, chaque nœud du reste du graphe sera distingué par un prédécesseur et une distance:

Pour terminer le processus d'initialisation, nous devons ajouter le nœud A aux nœuds non configurés pour qu'il soit sélectionné en premier lors de l'étape d'évaluation. Gardez à l'esprit que l'ensemble de nœuds installés est toujours vide.

2.2. Évaluation

Maintenant que notre graphe est initialisé, nous choisissons le nœud avec la distance la plus basse de l'ensemble non défini, puis nous évaluons tous les nœuds adjacents qui ne sont pas dans des nœuds établis:

L'idée est d'ajouter le poids du bord à la distance du nœud d'évaluation, puis de le comparer à la distance de la destination. par exemple pour le nœud B, 0 + 10 est inférieur à INFINITY, donc la nouvelle distance pour le nœud B est 10, et le nouveau prédécesseur est A, il en va de même pour le nœud C.

Le nœud A est ensuite déplacé de l'ensemble de nœuds non définis vers les nœuds installés.

Les nœuds B et C sont ajoutés aux nœuds non définis car ils peuvent être atteints, mais ils doivent être évalués.

Maintenant que nous avons deux nœuds dans l'ensemble non défini, nous choisissons celui avec la distance la plus faible (nœud B), puis nous répétons jusqu'à ce que nous réglions tous les nœuds du graphe:

Voici un tableau qui résume les itérations qui ont été effectuées lors des étapes d'évaluation:

Itération Instable Colonisé EvaluationNode UNE B C E F
1 UNE - UNE 0 A-10 A-15 X-∞ X-∞ X-∞
2 AVANT JC UNE B 0 A-10 A-15 B-22 X-∞ B-25
3 C, F, D UN B C 0 A-10 A-15 B-22 C-25 B-25
4 D, E, F A, B, C 0 A-10 A-15 B-22 J-24 D-23
5 E, F A B C D F 0 A-10 A-15 B-22 J-24 D-23
6 E A, B, C, D, F E 0 A-10 A-15 B-22 J-24 D-23
Final - TOUT AUCUN 0 A-10 A-15 B-22 J-24 D-23

La notation B-22, par exemple, signifie que le nœud B est le prédécesseur immédiat, avec une distance totale de 22 du nœud A.

Enfin, nous pouvons calculer les chemins les plus courts à partir du nœud A sont les suivants:

  • Nœud B: A -> B (distance totale = 10)
  • Nœud C: A -> C (distance totale = 15)
  • Nœud D: A -> B -> D (distance totale = 22)
  • Nœud E: A -> B -> D -> E (distance totale = 24)
  • Nœud F: A -> B -> D -> F (distance totale = 23)

3. Implémentation Java

Dans cette implémentation simple, nous allons représenter un graphe sous la forme d'un ensemble de nœuds:

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); 

Après le calcul, les attributs shortestPath et distance sont définis pour chaque nœud du graphique, nous pouvons les parcourir pour vérifier que les résultats correspondent exactement à ce qui a été trouvé dans la section précédente.

4. Conclusion

Dans cet article, nous avons vu comment l'algorithme Dijkstra résout le SPP et comment l'implémenter en Java.

La mise en œuvre de ce projet simple peut être trouvée dans le lien de projet GitHub suivant.