Dijkstra Shortest Path Algorithm in Java

1. Prezentare generală

Accentul din acest articol este cea mai scurtă problemă de cale (SPP), fiind una dintre problemele teoretice fundamentale cunoscute în teoria graficelor și modul în care algoritmul Dijkstra poate fi utilizat pentru a o rezolva.

Scopul de bază al algoritmului este de a determina calea cea mai scurtă dintre un nod de pornire și restul graficului.

2. Cea mai scurtă problemă de cale cu Dijkstra

Având în vedere un grafic ponderat pozitiv și un nod de pornire (A), Dijkstra determină cea mai scurtă cale și distanță de la sursă la toate destinațiile din grafic:

Ideea de bază a algoritmului Dijkstra este de a elimina continuu căile mai lungi între nodul de pornire și toate destinațiile posibile.

Pentru a urmări procesul, trebuie să avem două seturi distincte de noduri, stabilite și nesetate.

Nodurile așezate sunt cele cu o distanță minimă cunoscută de sursă. Setul de noduri nesetate adună noduri la care putem ajunge de la sursă, dar nu cunoaștem distanța minimă față de nodul de pornire.

Iată o listă cu pașii de urmat pentru a rezolva SPP cu Dijkstra:

  • Setați distanța pentru startNode la zero.
  • Setați toate celelalte distanțe la o valoare infinită.
  • Adăugăm startNode la setul de noduri nesetate .
  • În timp ce setul de noduri nesetate nu este gol, noi:
    • Alegeți un nod de evaluare din setul de noduri nesetate, nodul de evaluare ar trebui să fie cel cu cea mai mică distanță de sursă.
    • Calculați distanțe noi pentru a direcționa vecinii păstrând cea mai mică distanță la fiecare evaluare.
    • Adăugați vecinii care nu sunt încă stabiliți la setul de noduri nesetate.

Acești pași pot fi agregate în două etape, inițializare și evaluare. Să vedem cum se aplică acest lucru eșantionului de grafic:

2.1. Inițializare

Înainte de a începe explorarea tuturor căilor din grafic, trebuie mai întâi să inițializăm toate nodurile cu o distanță infinită și un predecesor necunoscut, cu excepția sursei.

Ca parte a procesului de inițializare, trebuie să atribuim valoarea 0 nodului A (știm că distanța de la nodul A la nodul A este 0 evident)

Deci, fiecare nod din restul graficului se va distinge cu un predecesor și o distanță:

Pentru a finaliza procesul de inițializare, trebuie să adăugăm nodul A la nodurile nesetate, setați-l pentru a fi ales mai întâi în etapa de evaluare. Rețineți, setul de noduri stabilite este încă gol.

2.2. Evaluare

Acum că avem graficul inițializat, alegem nodul cu cea mai mică distanță față de setul nesetat, apoi evaluăm toate nodurile adiacente care nu se află în noduri așezate:

Ideea este să adăugați greutatea muchiei la distanța nodului de evaluare, apoi să o comparați cu distanța destinației. de exemplu, pentru nodul B, 0 + 10 este mai mic decât INFINITY, deci noua distanță pentru nodul B este 10, iar noul predecesor este A, același lucru se aplică și nodului C.

Nodul A este apoi mutat de la nodurile nesetate setate la nodurile stabilite.

Nodurile B și C sunt adăugate la nodurile nerezolvate deoarece pot fi atinse, dar trebuie evaluate.

Acum că avem două noduri în setul nesetat, îl alegem pe cel cu cea mai mică distanță (nodul B), apoi repetăm ​​până când stabilim toate nodurile din grafic:

Iată un tabel care rezumă iterațiile care au fost efectuate în timpul etapelor de evaluare:

Repetare Necunoscut Stabilit Nod de evaluare A B C D E F
1 A - A 0 A-10 A-15 X-∞ X-∞ X-∞
2 B, C A 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
Final - TOATE NICI UNUL 0 A-10 A-15 B-22 D-24 D-23

Notarea B-22, de exemplu, înseamnă că nodul B este predecesorul imediat, cu o distanță totală de 22 de nodul A.

În cele din urmă, putem calcula cele mai scurte căi de la nodul A sunt după cum urmează:

  • Nodul B: A -> B (distanța totală = 10)
  • Nodul C: A -> C (distanța totală = 15)
  • Nodul D: A -> B -> D (distanța totală = 22)
  • Nodul E: A -> B -> D -> E (distanța totală = 24)
  • Nodul F: A -> B -> D -> F (distanța totală = 23)

3. Implementarea Java

În această simplă implementare vom reprezenta un grafic ca un set de noduri:

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

După calcul, atributele shortestPath și distance sunt setate pentru fiecare nod din grafic, putem itera prin ele pentru a verifica dacă rezultatele se potrivesc exact cu ceea ce a fost găsit în secțiunea anterioară.

4. Concluzie

În acest articol, am văzut cum algoritmul Dijkstra rezolvă SPP și cum să-l implementăm în Java.

Implementarea acestui proiect simplu poate fi găsită în link-ul următor al proiectului GitHub.