streamalism.org

1. Overzicht

De nadruk in dit artikel ligt op het kortste padprobleem (SPP), een van de fundamentele theoretische problemen die bekend zijn in de grafentheorie, en hoe het Dijkstra-algoritme kan worden gebruikt om dit op te lossen.

Het basisdoel van het algoritme is om het kortste pad tussen een startknooppunt en de rest van de grafiek te bepalen.

2. Kortste padprobleem met Dijkstra

Gegeven een positief gewogen grafiek en een startknooppunt (A), bepaalt Dijkstra het kortste pad en de kortste afstand van de bron naar alle bestemmingen in de grafiek:

Het kernidee van het Dijkstra-algoritme is om continu langere paden tussen het startknooppunt en alle mogelijke bestemmingen te elimineren.

Om het proces bij te houden, hebben we twee verschillende sets knooppunten nodig, geregeld en onrustig.

Afwikkelde knooppunten zijn de knooppunten met een bekende minimale afstand tot de bron. De set onzekere knooppunten verzamelt knooppunten die we vanaf de bron kunnen bereiken, maar we kennen de minimale afstand vanaf het startknooppunt niet.

Hier is een lijst met te volgen stappen om de SPP met Dijkstra op te lossen:

• Stel de afstand in op startNode tot nul.
• Stel alle andere afstanden in op een oneindige waarde.
• We voegen de startNode naar de onzekere knooppunten ingesteld.
• Hoewel de set onzekere knooppunten niet leeg is, kunnen we:
  • Kies een evaluatieknooppunt uit de niet-opgeloste knooppuntenset, het evaluatieknooppunt moet het knooppunt zijn met de laagste afstand tot de bron.
  • Bereken nieuwe afstanden tot directe buren door bij elke evaluatie de laagste afstand aan te houden.
  • Voeg buren die nog niet gesetteld zijn toe aan de onzekere knooppunten.

Deze stappen kunnen worden samengevoegd in twee fasen, initialisatie en evaluatie. Laten we eens kijken hoe dat van toepassing is op onze voorbeeldgrafiek:

2.1. Initialisatie

Voordat we alle paden in de grafiek gaan verkennen, moeten we eerst alle knooppunten met een oneindige afstand en een onbekende voorganger initialiseren, behalve de bron.

Als onderdeel van het initialisatieproces moeten we de waarde 0 toewijzen aan knooppunt A (we weten dat de afstand van knooppunt A tot knooppunt A uiteraard 0 is)

Dus elk knooppunt in de rest van de grafiek wordt onderscheiden met een voorganger en een afstand:

Om het initialisatieproces te voltooien, moeten we knooppunt A toevoegen aan de onzekere knooppunten die als eerste worden gekozen in de evaluatiestap. Houd er rekening mee dat de set vaste knooppunten nog steeds leeg is.

2.2. Evaluatie

Nu we onze grafiek hebben geïnitialiseerd, kiezen we het knooppunt met de laagste afstand van de onzekere set, en vervolgens evalueren we alle aangrenzende knooppunten die zich niet in vaste knooppunten bevinden:

Het idee is om het randgewicht toe te voegen aan de evaluatieknooppuntafstand en dit vervolgens te vergelijken met de afstand van de bestemming. bijv. voor knooppunt B is 0 + 10 lager dan INFINITY, dus de nieuwe afstand voor knooppunt B is 10, en de nieuwe voorganger is A, hetzelfde geldt voor knooppunt C.

Knooppunt A wordt dan verplaatst van de onrustige knooppunten die zijn ingesteld naar de vaste knooppunten.

Knooppunten B en C worden toegevoegd aan de onrustige knooppunten omdat ze kunnen worden bereikt, maar ze moeten worden geëvalueerd.

Nu we twee knooppunten hebben in de onzekere set, kiezen we degene met de laagste afstand (knooppunt B), en herhalen we totdat we alle knooppunten in de grafiek hebben geregeld:

Hier is een tabel met een overzicht van de iteraties die zijn uitgevoerd tijdens evaluatiestappen:

De notatie B-22 betekent bijvoorbeeld dat knooppunt B de directe voorganger is, met een totale afstand van 22 tot knooppunt A.

Ten slotte kunnen we de kortste paden vanaf knooppunt A als volgt berekenen:

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

3. Java-implementatie

In deze eenvoudige implementatie zullen we een grafiek weergeven als een reeks knooppunten:

openbare klasse Graph {privé Set knooppunten = nieuwe HashSet (); public void addNode (Node nodeA) {nodes.add (nodeA); } // getters en setters}

Een knooppunt kan worden beschreven met een naam, een LinkedList in verwijzing naar de Kortste weg, een afstand van de bron, en een aangrenzende lijst met de naam aangrenzende knooppunten:

public class Node {private String naam; private List shortestPath = nieuwe LinkedList (); privé Geheel getal afstand = Geheel getal.MAX_VALUE; Map aangrenzendeNodes = nieuwe HashMap (); public void addDestination (knooppuntbestemming, int afstand) {aangrenzendeNodes.put (bestemming, afstand); } public Node (String name) {this.name = name; } // getters en setters}

De aangrenzende knooppunten attribuut wordt gebruikt om directe buren te associëren met de randlengte. Dit is een vereenvoudigde implementatie van een aangrenzende lijst, die geschikter is voor het Dijkstra-algoritme dan de aangrenzende matrix.

Wat betreft de Kortste weg attribuut, het is een lijst met knooppunten die het kortste pad beschrijft dat wordt berekend vanaf het startknooppunt.

Standaard worden alle knooppuntafstanden geïnitialiseerd met Geheel getal.MAX_VALUE om een ​​oneindige afstand te simuleren zoals beschreven in de initialisatiestap.

Laten we nu het Dijkstra-algoritme implementeren:

openbare statische Graph berekenShortestPathFromSource (Graph-grafiek, knooppuntbron) {source.setDistance (0); Set settNodes = new HashSet (); Set unsettledNodes = nieuwe HashSet (); unsettledNodes.add (bron); while (unsettledNodes.size ()! = 0) {Node currentNode = getLowestDistanceNode (unsettledNodes); unsettledNodes.remove (currentNode); voor (Entry adjacencyPair: currentNode.getAd aangrenzendeNodes (). entrySet ()) {Node aangrenzendeNode = adjacencyPair.getKey (); Geheel getal edgeWeight = adjacencyPair.getValue (); if (! settNodes.contains (aangrenzendeNode)) {berekenMinimumDistance (aangrenzendeNode, edgeWeight, currentNode); unsettledNodes.add (aangrenzendeNode); }} settNodes.add (currentNode); } retourneer grafiek; }

De getLowestDistanceNode () methode, retourneert het knooppunt met de laagste afstand tot de onzekere knooppunten die zijn ingesteld, terwijl de berekenenMinimumafstand () methode vergelijkt de werkelijke afstand met de nieuw berekende afstand terwijl het nieuw onderzochte pad wordt gevolgd:

privé statisch knooppunt getLowestDistanceNode (Set unsettledNodes) {Knooppunt laagsteDistanceNode = null; int laagsteDistance = Geheel getal.MAX_VALUE; voor (Node node: unsettledNodes) {int nodeDistance = node.getDistance (); if (nodeDistance <laagsteDistance) {laagsteDistance = nodeDistance; laagsteDistanceNode = knooppunt; }} return leastDistanceNode; }

privé statische leegte CalculateMinimumDistance (Knoop evaluatieNode, geheel getal edgeWeigh, knooppunt sourceNode) {Geheel getal sourceDistance = sourceNode.getDistance (); if (sourceDistance + edgeWeigh <evaluatieNode.getDistance ()) {evaluatieNode.setDistance (sourceDistance + edgeWeigh); LinkedList shortestPath = nieuwe LinkedList (sourceNode.getShortestPath ()); shortestPath.add (sourceNode); evaluatieNode.setShortestPath (shortestPath); }}

Nu alle benodigde onderdelen aanwezig zijn, gaan we het Dijkstra-algoritme toepassen op de voorbeeldgrafiek die het onderwerp van het artikel is:

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

Na berekening is de Kortste weg en afstand attributen worden ingesteld voor elk knooppunt in de grafiek, we kunnen ze doorlopen om te verifiëren dat de resultaten exact overeenkomen met wat werd gevonden in de vorige sectie.

4. Conclusie

In dit artikel hebben we gezien hoe het Dijkstra-algoritme de SPP oplost en hoe het in Java kan worden geïmplementeerd.

De implementatie van dit eenvoudige project is te vinden in de volgende GitHub-projectlink.