Hur kan algoritm implementeras i Java med hjälp av en HEAP -datastruktur för effektiva kortaste sökvägsberäkningar?

Java har inte en inbyggd HEAP-datastruktur, men du kan använda "priorityqueue" som implementerar en min-heap (eller så kan du bygga din egen hög). Den vanligaste algoritmen som utnyttjar en hög för kortaste vägberäkningar är Dijkstras algoritm. Så här kan du implementera Dijkstras algoritm i Java med en "priorityqueue":

`` `Java

import java.util.*;

offentlig klass dijkstra {

offentlig statisk karta dijkstra (grafgraf, nodkälla) {

MAP avstånd =ny hashmap <> ();

PriorityQueue minheap =new PriorityQueue <> (Comparator.comParingInt (avstånd ::get)); // min-heap baserat på avstånd

// Initiera avstånd till oändligheten förutom källan

för (nodnod:graf.getNodes ()) {

avstånd.put (node, heltal.max_value);

}

avstånd.put (källa, 0);

minheap.add (källa);

medan (! minheap.isEmpty ()) {

Nodström =minheap.poll ();

för (kant kant:current.getedges ()) {

Nodgrann =edge.geto ();

int avstånd =avstånd.get (nuvarande) + edge.getweight ();

if (avstånd minheap.remove (granne); // Ta bort för att uppdatera prioritet

avstånd.put (granne, avstånd);

minheap.add (granne);

}

}

}

return avstånd;

}

// Helper -klasser för grafrepresentation

statisk klassgraf {

privat set noder =ny hashset <> ();

public void addNode (nodnod) {

noder.Add (nod);

}

public Set getNodes () {

returnera noder;

}

}

statisk klassnod {

privat strängnamn;

Privat lista kanter =ny ArrayList <> ();

public node (strängnamn) {

this.name =name;

}

public String getName () {return name;}

public void addEdge (Edge Edge) {

kanter.Add (kant);

}

public List getedges () {

returnera kanter;

}

@Åsidosätta

offentliga booleska lika (objekt obj) {

if (detta ==obj) returnerar sant;

if (obj ==null || getClass ()! =obj.getClass ()) returnera falsk;

Nodnod =(nod) obj;

returnobjekt.equals (namn, node.name);

}

@Åsidosätta

public int hashCode () {

returnobjekt.hash (namn);

}

}

statisk klasskant {

privat nod till;

privat int -vikt;

offentlig kant (nod till, int vikt) {

detta.to =till;

detta.vikt =vikt;

}

public node getTo () {

återgå till;

}

public int getweight () {

returvikt;

}

}

public static void main (String [] args) {

Grafgraf =ny graf ();

Nod a =ny nod ("a");

Nod B =ny nod ("B");

Nod C =ny nod ("C");

Nod d =ny nod ("d");

A.Addedge (ny kant (B, 4));

A.Addedge (ny kant (C, 2));

B.Addedge (ny kant (C, 1));

B.Addedge (ny kant (D, 5));

C.Addedge (ny kant (D, 8));

graf.AddNode (a);

graf.AddNode (B);

graf.AddNode (C);

graf.AddNode (D);

MAP avstånd =dijkstra (graf, a);

för (map.Entry post:avstånd.EntrySet ()) {

System.out.println ("Avstånd från a till" + post.getKey (). GetName () + ":" + post.getValue ());

}

}

}

`` `

Förklaring:

1. `graf`,` node`, `edge` klasser: Dessa representerar grafstrukturen. Klassen "Node" innehåller en lista över sina utgående "kant" -objekt.

2. `Dijkstra` Funktion: Detta implementerar Dijkstras algoritm.

- Det initialiserar en "HashMap" ("avstånd") för att lagra de kortaste avstånden från källnoden till alla andra noder. Ursprungligen är alla avstånd inställda på oändlighet utom för källan, som är 0.

- En "priorityqueue" används som en min-heap för att effektivt välja noden med det minsta avståndet. Komparatorn säkerställer att noder beställs av deras avstånd.

- Algoritmen tar iterativt bort noden med det minsta avståndet från högen. För var och en av sina grannar kontrollerar den om en kortare väg hittas och uppdaterar avståndet och högen därefter. "Ta bort" och "lägg till" -operationerna på "priorityqueue" upprätthåller högegenskapen effektivt (logaritmisk tid).

3. `Main` Funktion: Detta skapar en provgraf och kallar funktionen "Dijkstra". Resultatet visar det kortaste avståndet från noden "A" till alla andra noder.

Kom ihåg att hantera potentiella problem som negativa kantvikter (Dijkstras algoritm fungerar inte korrekt med dem; du skulle behöva Bellman-Ford-algoritmen istället) och koppla bort grafer. Detta förbättrade exempel hanterar "lika" och "hashcode" i klassen "Node" för att korrekt hantera "priorityqueue" och "hashmap" -hantering.