streamalism.org

1. Pregled

U ovom je članku naglasak stavljen na problem najkraćeg puta (SPP), koji je jedan od temeljnih teorijskih problema poznatih u teoriji grafova, i kako se algoritam Dijkstra može koristiti za njegovo rješavanje.

Osnovni cilj algoritma je odrediti najkraći put između početnog čvora i ostatka grafa.

2. Najkraći problem s Dijkstrom

S obzirom na pozitivno ponderirani graf i početni čvor (A), Dijkstra određuje najkraći put i udaljenost od izvora do svih odredišta na grafikonu:

Osnovna ideja Dijkstra algoritma je kontinuirano uklanjanje dužih staza između početnog čvora i svih mogućih odredišta.

Da bismo pratili proces, moramo imati dva različita skupa čvorova, naseljena i nepodmirena.

Useljeni čvorovi su oni s poznatom minimalnom udaljenostom od izvora. Neraspoređeni skup čvorova okuplja čvorove do kojih možemo doći iz izvora, ali ne znamo minimalnu udaljenost od početnog čvora.

Evo popisa koraka koje treba slijediti za rješavanje SPP-a s Dijkstrom:

• Postavite udaljenost na startNode na nulu.
• Sve ostale udaljenosti postavite na beskonačnu vrijednost.
• Dodamo startNode do neuređenih čvorova.
• Iako set neriješenih čvorova nije prazan mi:
  • Izaberite čvor procjene iz skupa neriješenih čvorova, čvor procjene trebao bi biti onaj s najmanjom udaljenostom od izvora.
  • Izračunajte nove udaljenosti do izravnih susjeda držeći najmanju udaljenost pri svakoj procjeni.
  • Dodajte susjede koji još nisu naseljeni u set neriješenih čvorova.

Ti se koraci mogu objediniti u dvije faze, inicijalizaciju i evaluaciju. Pogledajmo kako se to odnosi na naš uzorak grafa:

2.1. Inicijalizacija

Prije nego što započnemo s istraživanjem svih staza u grafu, prvo moramo inicijalizirati sve čvorove s beskonačnom udaljenostom i nepoznatim prethodnikom, osim izvora.

Kao dio procesa inicijalizacije, čvoru A moramo dodijeliti vrijednost 0 (znamo da je udaljenost od čvora A do čvora A očito 0)

Dakle, svaki čvor u ostatku grafa razlikovat će se s prethodnikom i udaljenostom:

Da bismo završili postupak inicijalizacije, trebamo dodati čvor A neriješenim čvorovima i postaviti ga tako da se prvo bira u koraku procjene. Imajte na umu da je skup smirenih čvorova još uvijek prazan.

2.2. Procjena

Sada kada je naš graf inicijaliziran, odabiremo čvor s najmanjom udaljenostom od neriješenog skupa, a zatim procjenjujemo sve susjedne čvorove koji nisu u ustaljenim čvorovima:

Ideja je dodati težinu ruba na udaljenost čvora procjene, a zatim je usporediti s udaljenošću odredišta. npr. za čvor B 0 + 10 je niži od INFINITY, tako da je nova udaljenost za čvor B 10, a novi prethodnik A, isto vrijedi i za čvor C.

Čvor A se zatim premješta iz neriješenih čvorova postavljenih u ustaljene čvorove.

Čvorovi B i C dodaju se nesređenim čvorovima jer se do njih može doći, ali ih treba procijeniti.

Sad kad imamo dva čvora u neuređenom skupu, odabiremo onaj s najmanjom udaljenostom (čvor B), a zatim ponavljamo dok ne podmirimo sve čvorove na grafikonu:

Evo tablice koja sažima ponavljanja izvršena tijekom koraka ocjenjivanja:

Oznaka B-22, na primjer, znači da je čvor B neposredni prethodnik, s ukupnom udaljenost 22 od čvora A.

Napokon, najkraći putovi od čvora A možemo izračunati kako slijedi:

• Čvor B: A -> B (ukupna udaljenost = 10)
• Čvor C: A -> C (ukupna udaljenost = 15)
• Čvor D: A -> B -> D (ukupna udaljenost = 22)
• Čvor E: A -> B -> D -> E (ukupna udaljenost = 24)
• Čvor F: A -> B -> D -> F (ukupna udaljenost = 23)

3. Implementacija Jave

U ovoj jednostavnoj implementaciji predstavit ćemo graf kao skup čvorova:

javna klasa Graph {private set čvorovi = new HashSet (); javna void addNode (čvor nodeA) {nodes.add (nodeA); } // geteri i postavljači}

Čvor se može opisati s Ime, a LinkedList u odnosu na najkraći put, a udaljenost iz izvora i imenovan popis susjedstva susjedni Čvorovi:

čvor javne klase {naziv privatnog niza; privatni popis shortestPath = novi LinkedList (); privatna Integer udaljenost = Integer.MAX_VALUE; Karta susjednih čvorova = nova HashMap (); javna praznina addDestination (odredište čvora, int udaljenost) {adjacentNodes.put (odredište, udaljenost); } javni čvor (naziv niza) {this.name = name; } // geteri i postavljači}

The susjedni Čvorovi atribut se koristi za povezivanje neposrednih susjeda s duljinom ruba. Ovo je pojednostavljena implementacija popisa susjedstva, koji je prikladniji za Dijkstra algoritam nego matrica susjedstva.

Što se tiče najkraći put atribut, to je popis čvorova koji opisuje najkraći put izračunat od početnog čvora.

Prema zadanim postavkama sve udaljenosti čvora inicijaliziraju se s Cijeli broj.MAX_VALUE za simulaciju beskonačne udaljenosti kako je opisano u koraku inicijalizacije.

Sada, implementirajmo Dijkstra algoritam:

javni statički graf convertShortestPathFromSource (graf grafa, izvor čvora) {source.setDistance (0); Postavi usedNodes = novi HashSet (); Postavi unsettledNodes = novi HashSet (); unsettledNodes.add (izvor); while (unsettledNodes.size ()! = 0) {Node currentNode = getLowestDistanceNode (unsettledNodes); unsettledNodes.remove (currentNode); za (Entry adjacencyPair: currentNode.getAdjacentNodes (). entrySet ()) {Node adjacentNode = adjacencyPair.getKey (); Cijeli broj edgeWeight = adjacencyPair.getValue (); if (! usedNodes.contens (adjacentNode)) {izračunatiMinimumDistance (adjacentNode, edgeWeight, currentNode); unsettledNodes.add (adjacentNode); }} usedNodes.add (currentNode); } graf povrata; }

The getLowestDistanceNode () metoda vraća čvor s najmanjom udaljenostom od postavljenih neriješenih čvorova, dok izračunajMinimumDistance () metoda uspoređuje stvarnu udaljenost s novoračunatom dok slijedi novoistraženi put:

privatni statički čvor getLowestDistanceNode (Postavi unsettledNodes) {Čvor najnižiDistancija = null; int lowerDistance = Integer.MAX_VALUE; za (čvor čvora: unsettledNodes) {int nodeDistance = node.getDistance (); if (nodeDistance <lowerDistance) {najmanja udaljenost = nodeDistance; lowerDistanceNode = čvor; }} vrati najnižiDistancode; }

privatna statička praznina CalculateMinimumDistance (čvor čvora, cjelobrojni edgeWeigh, čvor sourceNode) {Integer sourceDistance = sourceNode.getDistance (); if (sourceDistance + edgeWeigh <evaluationNode.getDistance ()) {evaluationNode.setDistance (sourceDistance + edgeWeigh); LinkedList shortestPath = novi LinkedList (sourceNode.getShortestPath ()); shortestPath.add (sourceNode); evaluationNode.setShortestPath (shortestPath); }}

Sad kad su svi potrebni dijelovi na mjestu, primijenimo algoritam Dijkstra na uzorku grafikona koji je predmet članka:

Čvor čvorA = novi čvor ("A"); Čvor čvorB = novi čvor ("B"); Čvor čvorC = novi čvor ("C"); Čvor čvorD = novi čvor ("D"); Čvor čvorE = novi čvor ("E"); Čvor čvorF = novi čvor ("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); Grafikon grafa = novi Grafikon (); graph.addNode (nodeA); graph.addNode (čvorB); graph.addNode (nodeC); graph.addNode (nodeD); graph.addNode (nodeE); graph.addNode (nodeF); graf = Dijkstra.calculateShortestPathFromSource (graf, čvorA); 

Nakon izračuna, najkraći put i udaljenost atributi su postavljeni za svaki čvor na grafikonu, možemo ih pregledati kako bismo provjerili odgovaraju li rezultati točno onome što je pronađeno u prethodnom odjeljku.

4. Zaključak

U ovom smo članku vidjeli kako algoritam Dijkstra rješava SPP i kako ga implementirati u Javi.

Provedbu ovog jednostavnog projekta možete pronaći na sljedećoj poveznici GitHub projekta.