Dijkstra kortaste banalgoritm i Java

1. Översikt

Tyngdpunkten i denna artikel är det kortaste vägproblemet (SPP), som är ett av de grundläggande teoretiska problemen som är kända inom grafteorin, och hur Dijkstra-algoritmen kan användas för att lösa det.

Algoritmens grundläggande mål är att bestämma den kortaste vägen mellan en startnod och resten av grafen.

2. Problem med kortaste vägen med Dijkstra

Med ett positivt viktat diagram och en startnod (A) bestämmer Dijkstra den kortaste vägen och avståndet från källan till alla destinationer i diagrammet:

Kärnidén med Dijkstra-algoritmen är att kontinuerligt eliminera längre vägar mellan startnoden och alla möjliga destinationer.

För att hålla reda på processen måste vi ha två olika noderuppsättningar, fasta och orörda.

Avgjorda noder är de med ett känt minimiavstånd från källan. De orubbliga noderuppsättningen samlar noder som vi kan nå från källan, men vi vet inte minsta avstånd från startnoden.

Här är en lista med steg att följa för att lösa SPP med Dijkstra:

  • Ställ avståndet till startNode till noll.
  • Ställ in alla andra avstånd till ett oändligt värde.
  • Vi lägger till startNode i den oredda noderuppsättningen .
  • Medan den orubbliga noderuppsättningen inte är tom gör vi:
    • Välj en utvärderingsnod från den oredda noderuppsättningen, utvärderingsnoden ska vara den med det lägsta avståndet från källan.
    • Beräkna nya avstånd till direkta grannar genom att hålla det lägsta avståndet vid varje utvärdering.
    • Lägg till grannar som ännu inte är bosatta i den oredda noden.

Dessa steg kan sammanställas i två steg, initialisering och utvärdering. Låt oss se hur det gäller för vårt exempeldiagram:

2.1. Initiering

Innan vi börjar utforska alla banor i diagrammet måste vi först initialisera alla noder med ett oändligt avstånd och en okänd föregångare, utom källan.

Som en del av initialiseringsprocessen måste vi tilldela värdet 0 till nod A (vi vet att avståndet från nod A till nod A uppenbarligen är 0)

Så, varje nod i resten av grafen kommer att särskiljas med en föregångare och ett avstånd:

För att avsluta initialiseringsprocessen måste vi lägga till nod A i de orubbliga noder som ställs in så att den väljs först i utvärderingssteget. Tänk på att den fasta noderuppsättningen fortfarande är tom.

2.2. Utvärdering

Nu när vi har initierat vårt diagram väljer vi noden med det lägsta avståndet från den orörda uppsättningen, och sedan utvärderar vi alla angränsande noder som inte finns i fasta noder:

Tanken är att lägga till kantvikten till utvärderingsnodavståndet och sedan jämföra den med målets avstånd. till exempel för nod B är 0 + 10 lägre än INFINITY, så det nya avståndet för nod B är 10, och den nya föregångaren är A, detsamma gäller för nod C.

Nod A flyttas sedan från de orörda noder som är inställda till de fasta noder.

Noder B och C läggs till de orubbliga noder eftersom de kan nås, men de behöver utvärderas.

Nu när vi har två noder i den orörda uppsättningen väljer vi den med det lägsta avståndet (nod B), sedan upprepar vi tills vi nöjer alla noder i diagrammet:

Här är en tabell som sammanfattar iterationerna som utfördes under utvärderingsstegen:

Iteration Orolig Fast EvaluationNode A B C D E F
1 A - A 0 A-10 A-15 X-∞ X-∞ X-∞
2 FÖRE KRISTUS 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
Slutlig - ALLT INGEN 0 A-10 A-15 B-22 D-24 D-23

Beteckningen B-22 betyder till exempel att nod B är den omedelbara föregångaren, med ett totalt avstånd på 22 från nod A.

Slutligen kan vi beräkna de kortaste banorna från nod A är följande:

  • Nod B: A -> B (totalt avstånd = 10)
  • Nod C: A -> C (totalt avstånd = 15)
  • Nod D: A -> B -> D (totalt avstånd = 22)
  • Nod E: A -> B -> D -> E (totalt avstånd = 24)
  • Nod F: A -> B -> D -> F (totalt avstånd = 23)

3. Java-implementering

I den här enkla implementeringen representerar vi en graf som en uppsättning noder:

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

En nod kan beskrivas med ett namn , en LinkedList med hänvisning till den kortaste vägen , ett avstånd från källan och en angränsningslista som heter angränsande noder :

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 }

Den adjacentNodes attribut används för att associera närmaste grannar med kantlängden. Detta är en förenklad implementering av en angränsningslista, som är mer lämplig för Dijkstra-algoritmen än angränsningsmatrisen.

När det gäller attributet shortestPath är det en lista med noder som beskriver den kortaste sökvägen beräknad från startnoden.

Som standard initialiseras alla nodavstånd med Integer.MAX_VALUE för att simulera ett oändligt avstånd som beskrivs i initialiseringssteget.

Låt oss nu implementera Dijkstra-algoritmen:

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

Den getLowestDistanceNode () metoden återgår noden med det lägsta avståndet från de oreglerade noder fastställs, medan calculateMinimumDistance () metoden jämför det verkliga avståndet med det nyligen beräknade ena när den följer den nyligen utforskats vägen:

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

Nu när alla nödvändiga bitar är på plats, låt oss tillämpa Dijkstra-algoritmen på exempeldiagrammet som är föremål för artikeln:

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

Efter beräkning ställs de kortaste väg- och avståndsattributen in för varje nod i grafen, vi kan itera igenom dem för att verifiera att resultaten matchar exakt vad som hittades i föregående avsnitt.

4. Slutsats

I den här artikeln har vi sett hur Dijkstra-algoritmen löser SPP och hur man implementerar den i Java.

Implementeringen av detta enkla projekt finns i följande GitHub-projektlänk.