Dijkstra Shortest Path Algorithm in Java

1. Panoramica

L'enfasi in questo articolo è il problema del percorso più breve (SPP), essendo uno dei problemi teorici fondamentali noti nella teoria dei grafi, e come l'algoritmo di Dijkstra può essere utilizzato per risolverlo.

L'obiettivo di base dell'algoritmo è determinare il percorso più breve tra un nodo iniziale e il resto del grafico.

2. Problema del percorso più breve con Dijkstra

Dato un grafico ponderato positivamente e un nodo iniziale (A), Dijkstra determina il percorso più breve e la distanza dalla sorgente a tutte le destinazioni nel grafico:

L'idea centrale dell'algoritmo Dijkstra è eliminare continuamente i percorsi più lunghi tra il nodo di partenza e tutte le possibili destinazioni.

Per tenere traccia del processo, abbiamo bisogno di due serie distinte di nodi, fissati e instabili.

I nodi stabilizzati sono quelli con una distanza minima nota dalla sorgente. Il set di nodi instabili raccoglie nodi che possiamo raggiungere dalla sorgente, ma non conosciamo la distanza minima dal nodo di partenza.

Ecco un elenco di passaggi da seguire per risolvere l'SPP con Dijkstra:

  • Imposta la distanza per startNode su zero.
  • Imposta tutte le altre distanze su un valore infinito.
  • Aggiungiamo startNode al set di nodi non regolati.
  • Anche se l'insieme dei nodi instabili non è vuoto, noi:
    • Scegli un nodo di valutazione dall'insieme di nodi non fissati, il nodo di valutazione dovrebbe essere quello con la distanza più bassa dalla sorgente.
    • Calcola nuove distanze per dirigere i vicini mantenendo la distanza più bassa ad ogni valutazione.
    • Aggiungi vicini che non sono stati ancora risolti all'insieme di nodi non sistemati.

Questi passaggi possono essere aggregati in due fasi, inizializzazione e valutazione. Vediamo come si applica al nostro grafico di esempio:

2.1. Inizializzazione

Prima di iniziare a esplorare tutti i percorsi nel grafico, dobbiamo prima inizializzare tutti i nodi con una distanza infinita e un predecessore sconosciuto, tranne la sorgente.

Come parte del processo di inizializzazione, dobbiamo assegnare il valore 0 al nodo A (sappiamo che la distanza dal nodo A al nodo A è ovviamente 0)

Quindi, ogni nodo nel resto del grafico verrà distinto con un predecessore e una distanza:

Per completare il processo di inizializzazione, è necessario aggiungere il nodo A ai nodi non impostati e impostarlo in modo che venga selezionato per primo nella fase di valutazione. Tieni presente che il set di nodi risolti è ancora vuoto.

2.2. Valutazione

Ora che abbiamo inizializzato il nostro grafico, selezioniamo il nodo con la distanza più bassa dall'insieme instabile, quindi valutiamo tutti i nodi adiacenti che non si trovano in nodi stabilizzati:

L'idea è di aggiungere il peso del bordo alla distanza del nodo di valutazione, quindi confrontarlo con la distanza della destinazione. ad esempio per il nodo B, 0 + 10 è inferiore a INFINITY, quindi la nuova distanza per il nodo B è 10, e il nuovo predecessore è A, lo stesso vale per il nodo C.

Il nodo A viene quindi spostato dai nodi instabili impostati ai nodi stabilizzati.

I nodi B e C vengono aggiunti ai nodi instabili perché possono essere raggiunti, ma devono essere valutati.

Ora che abbiamo due nodi nell'insieme instabile, scegliamo quello con la distanza più bassa (nodo B), quindi ripetiamo finché non sistemiamo tutti i nodi nel grafico:

Di seguito è riportata una tabella che riepiloga le iterazioni eseguite durante le fasi di valutazione:

Iterazione Sconvolto Stabilito EvaluationNode UN B C D E F
1 UN - UN 0 A-10 A-15 X-∞ X-∞ X-∞
2 AVANTI CRISTO UN 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 - TUTTI NESSUNA 0 A-10 A-15 B-22 D-24 D-23

La notazione B-22, ad esempio, significa che il nodo B è l'immediato predecessore, con una distanza totale di 22 dal nodo A.

Infine, possiamo calcolare i percorsi più brevi dal nodo A come segue:

  • Nodo B: A -> B (distanza totale = 10)
  • Nodo C: A -> C (distanza totale = 15)
  • Nodo D: A -> B -> D (distanza totale = 22)
  • Nodo E: A -> B -> D -> E (distanza totale = 24)
  • Nodo F: A -> B -> D -> F (distanza totale = 23)

3. Implementazione Java

In questa semplice implementazione rappresenteremo un grafico come un insieme di nodi:

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

Dopo il calcolo, gli attributi shortestPath e distance sono impostati per ogni nodo nel grafico, possiamo iterarli per verificare che i risultati corrispondano esattamente a quanto trovato nella sezione precedente.

4. Conclusione

In questo articolo, abbiamo visto come l'algoritmo Dijkstra risolve l'SPP e come implementarlo in Java.

L'implementazione di questo semplice progetto può essere trovata nel seguente collegamento al progetto GitHub.