Meny

Hvordan implementere Dijkstras algoritme i Java

  • Hoved
  • Annen
  • Hvordan implementere Dijkstras algoritme i Java

how implement dijkstra s algorithm java

Prøv Instrumentet Vårt For Å Eliminere Problemer

Denne opplæringen forklarer hvordan du implementerer Dijkstras algoritme i Java for å finne de korteste rutene i en graf eller et tre ved hjelp av eksempler:

I vår tidligere opplæring om Grafer i Java så vi at grafer brukes til å finne den korteste banen mellom nodene bortsett fra andre applikasjoner.

For å finne den korteste stien mellom to noder i en graf, bruker vi stort sett en algoritme kjent som “ Dijkstras algoritme ”. Denne algoritmen er fortsatt den mye brukte algoritmen for å finne de korteste rutene i en graf eller et tre.

=> Sjekk ALLE Java-opplæringsprogrammer her

Dijkstras algoritme i Java

Hva du vil lære:

Dijkstras algoritme i Java

Gitt en vektet graf og en start (kilde) toppunkt i grafen, brukes Dijkstras algoritme for å finne den korteste avstanden fra kildekoden til alle de andre nodene i grafen.

Som et resultat av den kjørende Dijkstras algoritme på en graf, får vi det korteste banetreet (SPT) med kildepunktet som rot.

I algoritmen til Dijkstra opprettholder vi to sett eller lister. Den ene inneholder hjørnene som er en del av det korteste stien (SPT), og den andre inneholder hjørner som evalueres for å bli inkludert i SPT. Derfor, for hver iterasjon, finner vi et toppunkt fra den andre listen som har den korteste banen.

Pseudokoden for Dijkstras korteste algoritme er gitt nedenfor.

beste programvare for å lage spill for nybegynnere

Pseudokode

Nedenfor er pseudokoden for denne algoritmen.

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

La oss nå ta et eksempel på en graf og illustrere Dijkstras korteste algoritme .

korteste banealgoritme

I utgangspunktet er SPT (Shortest Path Tree) settet til uendelig.

La oss starte med toppunkt 0. Så til å begynne med setter vi toppunktet 0 i sptSet.

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

Neste med toppunkt 0 i sptSet, vil vi utforske naboene. Vertices 1 og 2 er to tilstøtende noder på 0 med henholdsvis avstand 2 og 1.

tilstøtende noder

I figuren ovenfor har vi også oppdatert hvert tilstøtende toppunkt (1 og 2) med deres respektive avstand fra kildepunkt 0. Nå ser vi at toppunkt 2 har en minimumsavstand. Så deretter legger vi toppunkt 2 til sptSet. Vi utforsker også naboene til toppunkt 2.

tilstøtende toppunkt

Nå ser vi etter toppunktet med minimumsavstand og de som ikke er der i spt. Vi velger toppunkt 1 med avstand 2.

toppunkt med minimum avstand

Som vi ser i figuren ovenfor, er av alle tilstøtende noder på 2, 0 og 1 allerede i sptSet, så vi ignorerer dem. Ut av de tilstøtende nodene 5 og 3 har 5 den laveste kostnaden. Så vi legger det til sptSet og utforsk de tilstøtende nodene.

tilstøtende noder på 2, 0

I figuren ovenfor ser vi at bortsett fra noder 3 og 4, er alle andre noder i sptSet. Av 3 og 4 har node 3 den laveste kostnaden. Så vi setter den i sptSet.

noder 3 og 4

Som vist ovenfor har vi bare ett toppunkt igjen, dvs. 4 og avstanden fra rotnoden er 16. Til slutt setter vi den i sptSet for å få den endelige sptSet = {0, 2, 1, 5, 3, 4} at gir oss avstanden til hvert toppunkt fra kildekoden 0.

Implementering av Dijkstras algoritme i Java

Implementering av Dijkstras korteste algoritme i Java kan oppnås på to måter. Vi kan enten bruke prioritetskøer og nærhetsliste, eller vi kan bruke nærliggende matrise og matriser.

I denne delen vil vi se begge implementeringene.

Bruke en prioritert kø

I denne implementeringen bruker vi prioritetskøen til å lagre toppunktene med kortest avstand. Grafen er definert ved hjelp av adjacency-listen. Et eksempel på 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

Produksjon:

prioritetskø - utgang

Bruke Adjacency Matrix

I denne tilnærmingen bruker vi tilknytningsmatrisen til å representere grafen. For spt set bruker vi arrays.

Følgende program viser denne implementeringen.

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

Produksjon:

Adjacency Matrix - utgang

ofte stilte spørsmål

Q # 1) Fungerer Dijkstra for ikke-rettet grafer?

Svar: Hvis grafen er rettet eller ikke-rettet, spiller ikke noen rolle i tilfelle av Dijkstras algoritme. Denne algoritmen er bare bekymret for hjørnene i grafen og vektene.

Q # 2) Hva er tidskompleksiteten til Dijkstras algoritme?

Svar: Time Complexity of Dijkstra’s Algorithm is O (V 2). Når den implementeres med minprioritetskøen, kommer tidskompleksiteten til denne algoritmen 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 likhet med Prims algoritme for å finne minimumstreet (MST), starter disse algoritmene også fra et rotpunkt, og velger alltid det mest optimale toppunktet med minstestien.

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

Svar: Det er ingen av dem. Men ettersom Dijkstras algoritme bruker en prioritert kø for implementeringen, kan den sees på nær BFS.

Spørsmål nr. 5) Hvor brukes Dijkstra-algoritmen?

Svar: Den brukes hovedsakelig i rutingsprotokoller, da det hjelper å finne den korteste banen fra en node til en annen node.

Konklusjon

I denne veiledningen har vi diskutert Dijkstras algoritme. Vi bruker denne algoritmen for å finne den korteste banen fra rotnoden til de andre nodene i grafen eller et tre.

Vi implementerer vanligvis Dijkstras algoritme ved hjelp av en Priority-kø, da vi må finne minimumsveien. Vi kan også implementere denne algoritmen ved hjelp av adjacency-matrisen. Vi har diskutert begge disse tilnærmingene i denne opplæringen.

Vi håper du vil finne denne veiledningen nyttig.

=> Besøk her for å se Java Training Series for alle

Anbefalt lesing

^