Menu

Sådan implementeres Dijkstras algoritme i Java

how implement dijkstra s algorithm java

Prøv Vores Instrument Til At Fjerne Problemer

Denne vejledning forklarer, hvordan Dijkstras algoritme implementeres i Java for at finde de korteste ruter i en graf eller et træ ved hjælp af eksempler:

I vores tidligere tutorial om Grafer i Java så vi, at grafer bruges til at finde den korteste sti mellem knudepunkterne bortset fra andre applikationer.

For at finde den korteste sti mellem to noder i en graf bruger vi hovedsagelig en algoritme kendt som “ Dijkstras algoritme ”. Denne algoritme forbliver den almindeligt anvendte algoritme til at finde de korteste ruter i en graf eller et træ.

=> Tjek ALLE Java-tutorials her

Dijkstras algoritme i Java

Hvad du vil lære:

Dijkstras algoritme i Java

Med en vægtet graf og en start (kilde) toppunkt i grafen bruges Dijkstras algoritme til at finde den korteste afstand fra kildeknudepunktet til alle de andre noder i grafen.

Som et resultat af den kørende Dijkstras algoritme på en graf opnår vi det korteste stamtræ (SPT) med kildepunktet som rod.

I Dijkstras algoritme opretholder vi to sæt eller lister. Den ene indeholder hjørner, der er en del af det korteste stamtræ (SPT), og den anden indeholder hjørner, der evalueres for at blive inkluderet i SPT. Derfor finder vi for hver iteration et toppunkt fra den anden liste, der har den korteste vej.

Pseudokoden til Dijkstras korteste sti-algoritme er angivet nedenfor.

hvilket program åbner en eps-fil

Pseudokode

Nedenfor er pseudokoden for denne algoritme.

procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue PQueue path (S) <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path (U) + edge_weight(U, V) if tempDistance < path (V) path (V) <- tempDistance previous(V) <- U return path(), previous() end

Lad os nu tage en eksempeldiagram og illustrere Dijkstras korteste sti-algoritme .

korteste sti-algoritme

Oprindeligt er SPT (Shortest Path Tree) indstillet til uendelig.

Lad os starte med toppunkt 0. Så til at begynde med placerer vi toppunktet 0 i sptSet.

sptSet = {0, INF, INF, INF, INF, INF}.

Dernæst med toppunkt 0 i sptSet, vil vi udforske dets naboer. Højdepunkter 1 og 2 er to tilstødende knudepunkter på 0 med henholdsvis afstand 2 og 1.

tilstødende noder

I ovenstående figur har vi også opdateret hvert tilstødende toppunkt (1 og 2) med deres respektive afstand til kildepunkt 0. Nu ser vi, at toppunkt 2 har en minimumsafstand. Så næste tilføjer vi toppunkt 2 til sptSet. Vi udforsker også naboerne til toppunkt 2.

tilstødende toppunkt

Nu ser vi efter toppunktet med minimumsafstand og dem, der ikke er der i spt. Vi vælger toppunkt 1 med afstand 2.

toppunkt med minimum afstand

Som vi ser i ovenstående figur, er ud af alle de tilstødende noder på 2, 0 og 1 allerede i sptSet, så vi ignorerer dem. Ud af de tilstødende knudepunkter 5 og 3 har 5 de laveste omkostninger. Så vi tilføjer det til sptSet og udforsker de tilstødende noder.

tilstødende noder på 2, 0

I ovenstående figur ser vi, at bortset fra knudepunkter 3 og 4 er alle de andre knudepunkter i sptSet. Ud af 3 og 4 har knudepunkt 3 de laveste omkostninger. Så vi sætter det i sptSet.

knudepunkter 3 og 4

Som vist ovenfor har vi nu kun et toppunkt tilbage dvs. 4 og afstanden fra rodknudepunktet er 16. Endelig sætter vi det i sptSet for at få det endelige sptSet = {0, 2, 1, 5, 3, 4} at giver os afstanden for hvert toppunkt fra kildeknudepunktet 0.

Implementering af Dijkstras algoritme i Java

Implementering af Dijkstras korteste stiealgoritme i Java kan opnås på to måder. Vi kan enten bruge prioritetskøer og nærhedsliste, eller vi kan bruge nærhedsmatrix og arrays.

I dette afsnit vil vi se begge implementeringer.

Brug af en prioritetskø

I denne implementering bruger vi prioritetskøen til at gemme hjørnerne med den korteste afstand. Grafen defineres ved hjælp af nærhedslisten. Et eksempel på et program er vist nedenfor.

import java.util.*; class Graph_pq { int dist(); Set visited; PriorityQueue pqueue; int V; // Number of vertices List adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int(V); visited = new HashSet(); pqueue = new PriorityQueue(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i adj_list = new ArrayList(); // Initialize adjacency list for every node in the graph for (int i = 0; i

Produktion:

prioritetskø - output

Brug af Adjacency Matrix

I denne tilgang bruger vi adjacency matrix til at repræsentere grafen. Til spt-sæt bruger vi arrays.

Følgende program viser denne implementering.

import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array(), Boolean sptSet()) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v

Produktion:

Adjacency Matrix - output

Ofte stillede spørgsmål

Spørgsmål nr. 1) Fungerer Dijkstra for ikke-rettede grafer?

Svar: Hvis grafen er rettet eller ikke-rettet, betyder det ikke noget i tilfældet med Dijkstras algoritme. Denne algoritme er kun bekymret for hjørnerne i grafen og vægtene.

Q # 2) Hvad er tidskompleksiteten af ​​Dijkstras algoritme?

Svar: Tidskompleksitet af Dijkstras algoritme er O (V 2). Når den implementeres med min-prioritetskøen, kommer tidskompleksiteten af ​​denne algoritme ned til O (V + E l og V).

Q # 3) Er Dijkstra en grådig algoritme?

Svar: Ja, Dijkstra er en grådig algoritme. I lighed med Prims algoritme til at finde det minimale spændende træ (MST) starter disse algoritmer også fra et rodpunkt, og vælger altid det mest optimale toppunkt med den minimale sti.

Spørgsmål nr. 4) Er Dijkstra DFS eller BFS?

Svar: Det er ingen af ​​dem. Men da Dijkstras algoritme bruger en prioritetskø til implementeringen, kan den ses som tæt på BFS.

Spørgsmål nr. 5) Hvor anvendes Dijkstra-algoritmen?

Svar: Det bruges hovedsageligt til routingprotokoller, da det hjælper med at finde den korteste sti fra en node til en anden node.

Konklusion

I denne vejledning har vi diskuteret Dijkstras algoritme. Vi bruger denne algoritme til at finde den korteste sti fra rodnoden til de andre noder i grafen eller et træ.

Vi implementerer normalt Dijkstras algoritme ved hjælp af en prioritetskø, da vi skal finde den minimale sti. Vi kan også implementere denne algoritme ved hjælp af adjacency matrix. Vi har diskuteret begge disse tilgange i denne vejledning.

Vi håber, du vil finde denne tutorial nyttig.

=> Besøg her for at se Java Training Series for alle

Anbefalet læsning

^