streamalism.org

1. Prehľad

V tomto článku sa kladie dôraz na problém s najkratšou cestou (SPP), ktorý je jedným zo základných teoretických problémov známych v teórii grafov a ako je možné na jeho riešenie použiť algoritmus Dijkstra.

Základným cieľom algoritmu je určiť najkratšiu cestu medzi počiatočným uzlom a zvyškom grafu.

2. Problém s najkratšou cestou s Dijkstrou

Vzhľadom na kladne vážený graf a počiatočný uzol (A) určuje Dijkstra najkratšiu cestu a vzdialenosť od zdroja ku všetkým cieľom v grafe:

Základnou myšlienkou Dijkstraho algoritmu je kontinuálne eliminovať dlhšie cesty medzi východiskovým uzlom a všetkými možnými cieľmi.

Na sledovanie procesu potrebujeme mať dve odlišné sady uzlov, usadené a nevyrovnané.

Usadené uzly sú tie, ktoré majú známu minimálnu vzdialenosť od zdroja. Sada nevyriešených uzlov zhromažďuje uzly, na ktoré sa môžeme dostať zo zdroja, ale nepoznáme minimálnu vzdialenosť od počiatočného uzla.

Tu je zoznam krokov, ktoré treba dodržať pri riešení SPP s Dijkstra:

• Nastaviť vzdialenosť na startNode na nulu.
• Nastavte všetky ostatné vzdialenosti na nekonečnú hodnotu.
• Pridáme startNode do množiny nevyriešených uzlov.
• Aj keď sada nevyriešených uzlov nie je prázdna, vykonáme:
  • Vyberte vyhodnocovací uzol zo sady nevyriešených uzlov. Hodnotiaci uzol by mal byť uzol s najnižšou vzdialenosťou od zdroja.
  • Vypočítajte nové vzdialenosti pre priamych susedov tak, že pri každom vyhodnotení zachováte najnižšiu vzdialenosť.
  • Do sady nevyriešených uzlov pridajte susedov, ktorí ešte nie sú usadení.

Tieto kroky možno agregovať do dvoch fáz, inicializácie a vyhodnotenia. Pozrime sa, ako to platí pre náš vzorový graf:

2.1. Inicializácia

Predtým, ako začneme skúmať všetky cesty v grafe, je potrebné najskôr inicializovať všetky uzly s nekonečnou vzdialenosťou a neznámym predchodcom, okrem zdroja.

V rámci procesu inicializácie musíme uzlu A priradiť hodnotu 0 (vieme, že vzdialenosť od uzla A k uzlu A je samozrejme 0)

Každý uzol vo zvyšku grafu sa teda bude rozlišovať od predchodcu a vzdialenosti:

Na dokončenie procesu inicializácie musíme pridať uzol A do nevyriešených uzlov a nastaviť ho tak, aby bol najskôr vybraný v kroku vyhodnotenia. Majte na pamäti, že sada usadených uzlov je stále prázdna.

2.2. Vyhodnotenie

Teraz, keď máme náš graf inicializovaný, vyberieme uzol s najnižšou vzdialenosťou od nevyrovnanej množiny a potom vyhodnotíme všetky susedné uzly, ktoré nie sú v usadených uzloch:

Ide o pridanie hmotnosti okraja k vzdialenosti hodnotiaceho uzla a jeho porovnanie so vzdialenosťou cieľa. napr. pre uzol B je 0 + 10 nižšia ako INFINITY, takže nová vzdialenosť pre uzol B je 10 a nový predchodca je A, to isté platí pre uzol C.

Uzol A sa potom presunie z nevybavených uzlov nastavených na usadené uzly.

Uzly B a C sa pridávajú k nevyrovnaným uzlom, pretože sú dosiahnuteľné, ale je potrebné ich vyhodnotiť.

Teraz, keď máme v nevyrovnanej množine dva uzly, vyberieme ten s najmenšou vzdialenosťou (uzol B), potom opakujeme, kým nevyrovnáme všetky uzly v grafe:

Tu je tabuľka, ktorá sumarizuje iterácie, ktoré boli vykonané počas krokov hodnotenia:

Napríklad zápis B-22 znamená, že uzol B je bezprostredným predchodcom s celkovou vzdialenosťou 22 od uzla A.

Nakoniec môžeme vypočítať najkratšie cesty z uzla A:

• Uzol B: A -> B (celková vzdialenosť = 10)
• Uzol C: A -> C (celková vzdialenosť = 15)
• Uzol D: A -> B -> D (celková vzdialenosť = 22)
• Uzol E: A -> B -> D -> E (celková vzdialenosť = 24)
• Uzol F: A -> B -> D -> F (celková vzdialenosť = 23)

3. Implementácia Java

V tejto jednoduchej implementácii budeme reprezentovať graf ako množinu uzlov:

verejná trieda Graph {private Set nodes = new HashSet (); public void addNode (Node nodeA) {nodes.add (nodeA); } // zakladatelia a zakladatelia}

Uzol možno opísať pomocou a názov, a LinkedList v súvislosti s najkratšia cesta, a vzdialenosť zo zdroja a pomenovaný zoznam susedstva priľahlé uzly:

verejná trieda Uzol {súkromné ​​meno reťazca; private List shortestPath = new LinkedList (); private integer distance = Integer.MAX_VALUE; Mapa priľahlých uzlov = nová HashMap (); public void addDestination (cieľový uzol, int. vzdialenosť) {susednýNodes.put (cieľový, vzdialenosť); } verejný uzol (názov reťazca) {this.name = meno; } // zakladatelia a zakladatelia}

The priľahlé uzly atribút sa používa na priradenie bezprostredných susedov k dĺžke okraja. Toto je zjednodušená implementácia zoznamu susednosti, ktorá je pre Dijkstrov algoritmus vhodnejšia ako matica susednosti.

Pokiaľ ide o najkratšia cesta atribút, je to zoznam uzlov, ktorý popisuje najkratšiu cestu vypočítanú od východiskového uzla.

Štandardne sú všetky vzdialenosti uzlov inicializované pomocou Celé číslo.MAX_VALUE simulovať nekonečnú vzdialenosť, ako je opísané v inicializačnom kroku.

Teraz poďme implementovať Dijkstraov algoritmus:

verejný statický graf Calc CalcShortestPathFromSource (graf grafu, zdroj uzla) {source.setDistance (0); Nastaviť SetNode = new HashSet (); Set unsettledNodes = new HashSet (); unsettledNodes.add (zdroj); while (unsettledNodes.size ()! = 0) {Node currentNode = getLowestDistanceNode (unsettledNodes); unsettledNodes.remove (currentNode); pre (Entry adjacencyPair: currentNode.getAdjacentNodes (). entrySet ()) {Node NeighborNode = adjacencyPair.getKey (); Celé číslo edgeWeight = adjacencyPair.getValue (); if (! vysporiadanéNódy.obsahuje (susediaceNode)) {vypočítaťMinimálnuDistenciu (susediaceNode, edgeWeight, currentNode); unsettledNodes.add (NeighborNode); }} usedNodes.add (currentNode); } návratový graf; }

The getLowestDistanceNode () metóda vracia uzol s najmenšou vzdialenosťou od množiny nevyriešených uzlov, zatiaľ čo CalculateMinimumDistance () metóda porovnáva skutočnú vzdialenosť s novo vypočítanou, pričom sleduje novo preskúmanú cestu:

súkromný statický uzol getLowestDistanceNode (Set unsettledNodes) {Node lowerDistanceNode = null; int lowerDistance = Integer.MAX_VALUE; pre (Uzol uzla: unsettledNodes) {int nodeDistance = node.getDistance (); if (nodeDistance <lowerDistance) {lowerDistance = nodeDistance; lowerDistanceNode = uzol; }} vratit najnižšíDistanceNode; }

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 = nový LinkedList (sourceNode.getShortestPath ()); shortestPath.add (sourceNode); EvaluationNode.setShortestPath (shortestPath); }}

Teraz, keď sú všetky potrebné kúsky na mieste, použijeme Dijkstraov algoritmus na ukážkový graf, ktorý je predmetom článku:

Uzol nodeA = nový uzol ("A"); Uzol nodeB = nový uzol ("B"); Uzol nodeC = nový uzol ("C"); Uzol nodeD = nový uzol ("D"); Uzol nodeE = nový uzol ("E"); Uzol nodeF = nový Uzol ("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); Graf graf = nový Graf (); graph.addNode (nodeA); graph.addNode (nodeB); graph.addNode (nodeC); graph.addNode (nodeD); graph.addNode (nodeE); graph.addNode (nodeF); graph = Dijkstra.calculateShortestPathFromSource (graf, nodeA); 

Po výpočte najkratšia cesta a vzdialenosť atribúty sú nastavené pre každý uzol v grafe, môžeme ich iterovať, aby sme overili, či sa výsledky presne zhodujú s výsledkami v predchádzajúcej časti.

4. Záver

V tomto článku sme videli, ako Dijkstra algoritmus rieši SPP a ako ho implementovať v Jave.

Implementáciu tohto jednoduchého projektu nájdete v nasledujúcom odkaze na projekt GitHub.