streamalism.org

1. Oversikt

Vekten i denne artikkelen er det korteste sti-problemet (SPP), som er et av de grunnleggende teoretiske problemene som er kjent i grafteorien, og hvordan Dijkstra-algoritmen kan brukes til å løse den.

Det grunnleggende målet for algoritmen er å bestemme den korteste banen mellom en startnode og resten av grafen.

2. Problem med korteste vei med Dijkstra

Gitt en vektet graf og en startnode (A), bestemmer Dijkstra den korteste banen og avstanden fra kilden til alle destinasjoner i grafen:

Kjernetanken til Dijkstra-algoritmen er å kontinuerlig eliminere lengre baner mellom startnoden og alle mulige destinasjoner.

For å holde oversikt over prosessen, må vi ha to forskjellige sett med noder, avgjort og urolig.

Avgjorte noder er de med en kjent minimumsavstand fra kilden. De usikrede nodesettene samler noder som vi kan nå fra kilden, men vi vet ikke minimumsavstanden fra startnoden.

Her er en liste over trinn som skal følges for å løse SPP med Dijkstra:

• Sett avstand til startNode til null.
• Sett alle andre avstander til en uendelig verdi.
• Vi legger til startNode til de uoppgjorte nodene.
• Mens det uoppgjorte nodesettet ikke er tomt, gjør vi:
  • Velg en evalueringsknute fra det usettede nodesettet, evalueringsnoden skal være den med lavest avstand fra kilden.
  • Beregn nye avstander til direkte naboer ved å holde den laveste avstanden ved hver evaluering.
  • Legg til naboer som ennå ikke er avgjort, til det usettede nodesettet.

Disse trinnene kan samles i to trinn, initialisering og evaluering. La oss se hvordan det gjelder eksemplet vårt:

2.1. Initialisering

Før vi begynner å utforske alle stier i grafen, må vi først initialisere alle noder med en uendelig avstand og en ukjent forgjenger, bortsett fra kilden.

Som en del av initialiseringsprosessen må vi tilordne verdien 0 til node A (vi vet at avstanden fra node A til node A er åpenbart 0)

Så hver node i resten av grafen vil bli skilt med en forgjenger og en avstand:

For å fullføre initialiseringsprosessen, må vi legge til node A i de usettede nodene, slik at den blir valgt først i evalueringstrinnet. Husk at settede nodesett fortsatt er tomt.

2.2. Evaluering

Nå som vi har initialisert grafen vår, velger vi noden med den laveste avstanden fra det usettede settet, og deretter evaluerer vi alle tilstøtende noder som ikke er i avgjorte noder:

Ideen er å legge til kantvekten til evalueringsnoden, og deretter sammenligne den med destinasjonens avstand. f.eks. for node B er 0 + 10 lavere enn INFINITY, så den nye avstanden for node B er 10, og den nye forgjengeren er A, det samme gjelder node C.

Node A flyttes deretter fra de usettede nodene som er satt til de avgjorte nodene.

Noder B og C legges til de uopprettede nodene fordi de kan nås, men de må evalueres.

Nå som vi har to noder i det usettede settet, velger vi den med laveste avstand (node ​​B), og deretter gjentar vi til vi legger alle noder i grafen:

Her er en tabell som oppsummerer iterasjonene som ble utført under evalueringstrinnene:

Notasjonen B-22 betyr for eksempel at node B er den nærmeste forgjengeren, med en total avstand på 22 fra node A.

Til slutt kan vi beregne de korteste banene fra node A er som følger:

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

3. Java-implementering

I denne enkle implementeringen vil vi representere en graf som et sett med noder:

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

En node kan beskrives med a Navn, a LinkedList med henvisning til korteste sti, a avstand fra kilden, og en tilknytningsliste med navn tilstøtende noder:

offentlig klasse Node {privat strengnavn; privat liste shortestPath = new LinkedList (); privat Heltallavstand = Heltall.MAX_VALUE; Kart tilstøtende knutepunkter = ny HashMap (); public void addDestination (Node-destinasjon, int-avstand) {tilstøtendeNodes.put (destinasjon, avstand); } offentlig node (strengnavn) {this.name = navn; } // getters og setters}

De tilstøtende noder attributt brukes til å knytte nærmeste naboer til kantlengde. Dette er en forenklet implementering av en adjacency-liste, som er mer egnet for Dijkstra-algoritmen enn adjacency-matrisen.

Når det gjelder korteste sti attributt, er det en liste over noder som beskriver den korteste banen beregnet fra startnoden.

Som standard initialiseres alle nodeavstander med Heltall.MAX_VALUE for å simulere en uendelig avstand som beskrevet i initialiseringstrinnet.

La oss nå implementere Dijkstra-algoritmen:

offentlig statisk Graf beregneShortestPathFromSource (Grafgraf, Nodekilde) {source.setDistance (0); Sett SettNodes = ny HashSet (); Set unsettledNodes = new HashSet (); unsettledNodes.add (kilde); mens (unsettledNodes.size ()! = 0) {Node currentNode = getLowestDistanceNode (unsettledNodes); unsettledNodes.remove (currentNode); for (Entry adjacencyPair: currentNode.getAdjacentNodes (). entrySet ()) {Node tilstøtendeNode = adjacencyPair.getKey (); Integer edgeWeight = adjacencyPair.getValue (); hvis (! SettNodes.contains (tilstøtendeNode)) {BeregnMinimumDistanse (tilstøtendeNode, kantvekt, nåværendeNode); unsettledNodes.add (tilstøtendeNode); }} SettNodes.add (currentNode); } returner graf; }

De getLowestDistanceNode () metoden, returnerer noden med den laveste avstanden fra det usettede nodesettet, mens beregneMinimumDistance () metoden sammenligner den faktiske avstanden med den nylig beregnede mens den følger den nylig utforskede banen:

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

privat statisk tomrom CalculateMinimumDistance (Node valuationNode, Integer edgeWeigh, Node sourceNode) {Integer sourceDistance = sourceNode.getDistance (); hvis (sourceDistance + edgeWeigh <valuationNode.getDistance ()) {valuationNode.setDistance (sourceDistance + edgeWeigh); LinkedList shortestPath = new LinkedList (sourceNode.getShortestPath ()); shortestPath.add (sourceNode); assessmentNode.setShortestPath (shortestPath); }}

Nå som alle nødvendige brikker er på plass, la oss bruke Dijkstra-algoritmen på eksempeldiagrammet som er gjenstand for artikkelen:

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

Etter beregning, korteste sti og avstand attributter er satt for hver node i grafen, kan vi gjenta dem for å verifisere at resultatene samsvarer nøyaktig med det som ble funnet i forrige avsnitt.

4. Konklusjon

I denne artikkelen har vi sett hvordan Dijkstra-algoritmen løser SPP, og hvordan du implementerer den i Java.

Implementeringen av dette enkle prosjektet finner du i følgende GitHub-prosjektlink.