Meny

Hur man implementerar Dijkstras algoritm i Java

  • Huvud
  • Övrig
  • Hur man implementerar Dijkstras algoritm i Java

how implement dijkstra s algorithm java

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning förklarar hur man implementerar Dijkstras algoritm i Java för att hitta de kortaste vägarna i en graf eller ett träd med hjälp av exempel:

I vår tidigare handledning om Grafer i Java såg vi att grafer används för att hitta den kortaste vägen mellan noder förutom andra applikationer.

För att hitta den kortaste vägen mellan två noder i en graf använder vi oftast en algoritm som kallas ” Dijkstras algoritm ”. Denna algoritm förblir den allmänt använda algoritmen för att hitta de kortaste vägarna i en graf eller ett träd.

=> Kontrollera ALLA Java-handledning här

Dijkstras algoritm i Java

Vad du kommer att lära dig:

Dijkstras algoritm i Java

Med tanke på ett viktat diagram och en startkälla (källa) i diagrammet används Dijkstras algoritm för att hitta det kortaste avståndet från källnoden till alla andra noder i diagrammet.

Som ett resultat av den löpande Dijkstras algoritm i en graf, får vi det kortaste stigträdet (SPT) med källpunkten som rot.

I Dijkstras algoritm upprätthåller vi två uppsättningar eller listor. En innehåller de hörn som är en del av det kortaste trädet (SPT) och den andra innehåller hörn som utvärderas för att ingå i SPT. Därför för varje iteration hittar vi ett toppunkt från den andra listan som har den kortaste vägen.

Nedan visas pseudokoden för Dijkstras kortaste algoritm.

gratis Windows-rengöringsprogram och reparation

Pseudokod

Nedan visas pseudokoden för denna algoritm.

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

Låt oss nu ta ett exempeldiagram och illustrera Dijkstras kortaste algoritm .

kortaste banalgoritmen

Ursprungligen är SPT (Shortest Path Tree) inställt på oändlighet.

Låt oss börja med vertex 0. Så till att börja med sätter vi vertex 0 i sptSet.

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

Nästa med vertex 0 i sptSet kommer vi att utforska dess grannar. Hörn 1 och 2 är två angränsande noder med 0 med avstånd 2 respektive 1.

intilliggande noder

I figuren ovan har vi också uppdaterat varje intilliggande toppunkt (1 och 2) med deras respektive avstånd från källpunkten 0. Nu ser vi att toppunkt 2 har ett minsta avstånd. Så nästa vi lägger toppunkt 2 till sptSet. Vi utforskar också grannarna till toppunkt 2.

intilliggande toppunkt

Nu letar vi efter toppunktet med minsta avstånd och de som inte finns där i spt. Vi väljer topp 1 med avstånd 2.

toppunkt med minsta avstånd

Som vi ser i figuren ovan är av alla intilliggande noder 2, 0 och 1 redan i sptSet så vi ignorerar dem. Av de intilliggande noderna 5 och 3 har 5 den lägsta kostnaden. Så vi lägger till det i sptSet och utforskar dess intilliggande noder.

intilliggande noder på 2, 0

I figuren ovan ser vi att förutom noder 3 och 4 är alla andra noder i sptSet. Av 3 och 4 har nod 3 den lägsta kostnaden. Så vi lägger det i sptSet.

noder 3 och 4

Som visas ovan har vi nu bara en topp kvar, dvs. 4 och dess avstånd från rotnoden är 16. Slutligen sätter vi det i sptSet för att få den slutliga sptSet = {0, 2, 1, 5, 3, 4} att ger oss avståndet för varje toppunkt från källnoden 0.

Implementering av Dijkstras algoritm i Java

Implementering av Dijkstras kortaste banalgoritm i Java kan uppnås på två sätt. Vi kan antingen använda prioritetsköer och närliggande lista eller så kan vi använda närliggande matris och matriser.

I detta avsnitt kommer vi att se båda implementeringarna.

Använda en prioriterad kö

I den här implementeringen använder vi prioritetskön för att lagra topparna med kortast avstånd. Grafen definieras med hjälp av listan över angränsningar. Ett exempelprogram visas nedan.

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ö - utdata

Använda Adjacency Matrix

I detta tillvägagångssätt använder vi adjacencymatrisen för att representera grafen. För spt set använder vi arrays.

Följande program visar denna 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

Vanliga frågor

F # 1) Fungerar Dijkstra för oriktade grafer?

Svar: Om diagrammet är riktat eller inte riktat spelar ingen roll i fallet med Dijkstras algoritm. Denna algoritm berör endast hörn i grafen och vikterna.

F # 2) Vad är tidskomplexiteten i Dijkstras algoritm?

Svar: Tidskomplexitet för Dijkstras algoritm är O (V 2). När den implementeras med min-prioritetskön, kommer tidskomplexiteten för denna algoritm ner till O (V + E l og V).

F # 3) Är Dijkstra en girig algoritm?

Svar: Ja, Dijkstra är en girig algoritm. I likhet med Prims algoritm för att hitta det minsta spännande trädet (MST) startar dessa algoritmer också från en rotkod och väljer alltid det mest optimala toppunktet med minsta väg.

F # 4) Är Dijkstra DFS eller BFS?

Svar: Det är varken. Men eftersom Dijkstras algoritm använder en prioritetskö för implementeringen kan den ses som nära BFS.

F # 5) Var används Dijkstra-algoritmen?

Svar: Den används mest i routingprotokoll eftersom det hjälper till att hitta den kortaste vägen från en nod till en annan nod.

Slutsats

I denna handledning har vi diskuterat Dijkstras algoritm. Vi använder den här algoritmen för att hitta den kortaste vägen från rotnoden till de andra noderna i diagrammet eller ett träd.

Vi implementerar vanligtvis Dijkstras algoritm med en prioritetskö eftersom vi måste hitta minsta väg. Vi kan också implementera denna algoritm med hjälp av adjacency matrisen. Vi har diskuterat båda dessa tillvägagångssätt i denna handledning.

Vi hoppas att du kommer att finna den här handledningen till hjälp.

=> Besök här för att se Java Training Series för alla

Rekommenderad läsning

^