streamalism.org

1. Oversigt

Vægten i denne artikel er det korteste sti-problem (SPP), der er et af de grundlæggende teoretiske problemer, der er kendt i grafteori, og hvordan Dijkstra-algoritmen kan bruges til at løse det.

Algoritmens grundlæggende mål er at bestemme den korteste sti mellem en startknude og resten af ​​grafen.

2. Korteste sti-problem med Dijkstra

Givet en positivt vægtet graf og en startknude (A) bestemmer Dijkstra den korteste sti og afstand fra kilden til alle destinationer i grafen:

Grundideen med Dijkstra-algoritmen er kontinuerligt at fjerne længere stier mellem startknudepunktet og alle mulige destinationer.

For at holde styr på processen er vi nødt til at have to forskellige sæt noder, afgjort og uafviklet.

Afregnede noder er dem med en kendt minimumsafstand fra kilden. De usikrede noder sæt samler noder, som vi kan nå fra kilden, men vi kender ikke den mindste afstand fra startknudepunktet.

Her er en liste over trin, der skal følges for at løse SPP med Dijkstra:

• Indstil afstand til startNode til nul.
• Indstil alle andre afstande til en uendelig værdi.
• Vi tilføjer startNode til det uoprettede nodesæt.
• Mens det usikrede nodesæt ikke er tomt, gør vi:
  • Vælg en evalueringsknude fra det usættede nodesæt, evalueringsnoden skal være den med den laveste afstand fra kilden.
  • Beregn nye afstande til direkte naboer ved at holde den laveste afstand ved hver evaluering.
  • Føj naboer, der endnu ikke er afgjort, til det usættede nodesæt.

Disse trin kan samles i to faser, initialisering og evaluering. Lad os se, hvordan gælder det for vores eksempeldiagram:

2.1. Initialisering

Før vi begynder at udforske alle stier i grafen, skal vi først initialisere alle noder med en uendelig afstand og en ukendt forgænger undtagen kilden.

Som en del af initialiseringsprocessen er vi nødt til at tildele værdien 0 til node A (vi ved, at afstanden fra node A til node A tydeligvis er 0)

Så hver knude i resten af ​​grafen skelnes med en forgænger og en afstand:

For at afslutte initialiseringsprocessen er vi nødt til at tilføje node A til de uafviklede noder, der indstilles til at blive valgt først i evalueringstrinnet. Husk, at det afgjorte nodesæt stadig er tomt.

2.2. Evaluering

Nu hvor vores graf er initialiseret, vælger vi noden med den laveste afstand fra det uafviklede sæt, så evaluerer vi alle tilstødende noder, der ikke er i afregnede noder:

Ideen er at tilføje kantvægten til evalueringsknudeafstanden og derefter sammenligne den med destinationens afstand. f.eks. for node B er 0 + 10 lavere end INFINITY, så den nye afstand for node B er 10, og den nye forgænger er A, det samme gælder node C.

Knude A flyttes derefter fra de usættede noder, der er indstillet til de afviklede noder.

Knudepunkterne B og C føjes til de uafviklede knudepunkter, fordi de kan nås, men de skal evalueres.

Nu hvor vi har to noder i det usættede sæt, vælger vi den med den laveste afstand (node ​​B), så gentager vi, indtil vi afregner alle noder i grafen:

Her er en tabel, der opsummerer gentagelserne, der blev udført under evalueringstrinnene:

Betegnelsen B-22 betyder for eksempel, at node B er den nærmeste forgænger med en samlet afstand på 22 fra node A.

Endelig kan vi beregne de korteste stier fra node A er som følger:

• Knude B: A -> B (total afstand = 10)
• Knude C: A -> C (total afstand = 15)
• Knude D: A -> B -> D (total afstand = 22)
• Knude E: A -> B -> D -> E (total afstand = 24)
• Knude F: A -> B -> D -> F (total afstand = 23)

3. Java-implementering

I denne enkle implementering repræsenterer vi en graf som et sæt noder:

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

En knude kan beskrives med en navn, a LinkedList med henvisning til korteste sti, a afstand fra kilden og en nærhedsliste navngivet tilstødende knuder:

offentlig klasse Node {privat strengnavn; privat liste shortestPath = ny LinkedList (); privat Heltalsafstand = Heltal.MAX_VALUE; Kort tilstødende knudepunkter = ny HashMap (); public void addDestination (Node destination, int afstand) {tilstødendeNodes.put (destination, afstand); } offentlig knude (strengnavn) {dette.navn = navn; } // getters og setters}

Det tilstødende knuder attribut bruges til at forbinde umiddelbare naboer med kantlængde. Dette er en forenklet implementering af en adjacency-liste, som er mere egnet til Dijkstra-algoritmen end adjacency-matrixen.

hvad angår korteste sti attribut, det er en liste over noder, der beskriver den korteste sti beregnet ud fra startnoden.

Som standard initialiseres alle knudeafstande med Heltal.MAX_VALUE at simulere en uendelig afstand som beskrevet i initialiseringstrinnet.

Lad os nu implementere Dijkstra-algoritmen:

offentlig statisk graf beregneShortestPathFromSource (grafgraf, nodekilde) {source.setDistance (0); Indstil SettNodes = ny HashSet (); Set unsettledNodes = new HashSet (); unsettledNodes.add (kilde); mens (unsettledNodes.size ()! = 0) {Node currentNode = getLowestDistanceNode (unsettledNodes); unsettledNodes.remove (nuværendeNode); for (Entry adjacencyPair: currentNode.getAdjacentNodes (). entrySet ()) {Node tilstødendeNode = adjacencyPair.getKey (); Integer edgeWeight = adjacencyPair.getValue (); hvis (! SettNodes.contains (tilstødendeNode)) {BeregnMinimumDistance (tilstødendeNode, kantvægt, nuværendeNode); unsettledNodes.add (tilstødendeNode); }} SettNodes.add (nuværendeNode); } returnere graf; }

Det getLowestDistanceNode () metode, returnerer noden med den laveste afstand fra det usættede nodesæt, mens beregneMinimumDistance () metode sammenligner den faktiske afstand med den nyberegnede, mens den følger den nyudforskede sti:

privat statisk knudepunkt getLowestDistanceNode (Set unsettledNodes) {Node leechsteDistanceNode = null; int lowerDistance = Integer.MAX_VALUE; for (Node node: unsettledNodes) {int nodeDistance = node.getDistance (); hvis (nodeDistance <laveste afstand) {laveste afstand = nodeDistance; lowerDistanceNode = node; }} returner lowestDistanceNode; }

privat statisk tomrum CalculateMinimumDistance (Node evalueringNode, Hele kant kant, Vej, Node kildeNode) {Heltal kildeDistance = kildeNode.getDistance (); hvis (sourceDistance + edgeWeigh <valuationNode.getDistance ()) {valuationNode.setDistance (sourceDistance + edgeWeigh); LinkedList shortestPath = ny LinkedList (sourceNode.getShortestPath ()); shortestPath.add (sourceNode); assessmentNode.setShortestPath (shortestPath); }}

Nu hvor alle de nødvendige stykker er på plads, lad os anvende Dijkstra-algoritmen på eksempeldiagrammet, der er genstand for artiklen:

Node nodeA = ny node ("A"); Node nodeB = ny node ("B"); Node nodeC = ny node ("C"); Node nodeD = ny node ("D"); Node nodeE = ny node ("E"); Node nodeF = ny 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); Grafgraf = ny graf (); graph.addNode (nodeA); graph.addNode (nodeB); graph.addNode (nodeC); graph.addNode (nodeD); graph.addNode (nodeE); graph.addNode (nodeF); graf = Dijkstra.calculateShortestPathFromSource (graf, nodeA); 

Efter beregning blev korteste sti og afstand attributter er indstillet for hver node i grafen, kan vi gentage dem for at kontrollere, at resultaterne matcher nøjagtigt det, der blev fundet i det foregående afsnit.

4. Konklusion

I denne artikel har vi set, hvordan Dijkstra-algoritmen løser SPP, og hvordan man implementerer den i Java.

Implementeringen af ​​dette enkle projekt kan findes i følgende GitHub-projektlink.