DIJKSTRA ALGORITHM JAVA - JAVA HANDLEDNING

Dijkstra algoritm är en av de framträdande algoritmerna för att hitta den kortaste vägen från källnoden till en destinationsnod. Den använder den giriga strategin för att hitta den kortaste vägen. Konceptet med Dijkstra-algoritmen är att hitta det kortaste avståndet (vägen) med början från källpunkten och att ignorera de längre avstånden medan du gör en uppdatering.

I det här avsnittet kommer vi att implementera Dijkstra algoritm i Java-program . Vi kommer också att diskutera dess användning och begränsningar.

Dijkstra Algoritm Steg

Steg 1: Alla noder ska markeras som obesökta.

Steg 2: Alla noder måste initieras med det 'oändliga' (ett stort antal) avståndet. Startnoden måste initieras med noll.

Steg 3: Markera startnoden som den aktuella noden.

Steg 4: Från den aktuella noden, analysera alla dess grannar som inte har besökts ännu, och beräkna deras avstånd genom att lägga till vikten på kanten, vilket upprättar kopplingen mellan den aktuella noden och grannoden till det aktuella avståndet för den aktuella noden.

Steg 5: Jämför nu det nyligen beräknade avståndet med avståndet som tilldelats den närliggande noden, och behandla det som det aktuella avståndet för den närliggande noden,

Steg 6: Därefter beaktas de omgivande grannarna till den aktuella noden, som inte har besökts, och de aktuella noderna markeras som besökta.

Steg 7: När slutnoden är markerad som besökt, då har algoritmen gjort sitt jobb; annat,

Steg 8: Välj den obesökta noden som har tilldelats minimiavståndet och behandla den som den nya nuvarande noden. Efter det, börja om från steg 4.

Dijkstra Algoritm Pseudokod

 Method Dijkstra(G, s): // G is graph, s is source distance[s] -&gt; 0 // Distance from the source to source is always 0 for every vertex vx in the Graph G: // doing the initialization work { if vx ? s { // Unknown distance function from source to each node set to infinity distance[vx] -&gt; infinity } add vx to Queue Q // Initially, all the nodes are in Q } // The while loop Untill the Q is not empty: { // During the first run, this vertex is the source or starting node vx = vertex in Q with the minimum distance[vx] delete vx from Q } // where the neighbor ux has not been deleted yet from Q. for each neighbor ux of vx: alt = distance[vx] + length(vx, ux) // A path with lesser weight (shorter path), to ux is found if alt <distance[ux]: distance[ux]="alt" updating the distance of ux return dist[] end method < pre> <h2>Implementation of Dijkstra Algorithm</h2> <p>The following code implements the Dijkstra Algorithm using the diagram mentioned below.</p> <img src="//techcodeview.com/img/java-tutorial/65/dijkstra-algorithm-java.webp" alt="Dijkstra Algorithm Java"> <p> <strong>FileName:</strong> DijkstraExample.java</p> <pre> // A Java program that finds the shortest path using Dijkstra&apos;s algorithm. // The program uses the adjacency matrix for the representation of a graph // import statements import java.util.*; import java.io.*; import java.lang.*; public class DijkstraExample { // A utility method to compute the vertex with the distance value, which is minimum // from the group of vertices that has not been included yet static final int totalVertex = 9; int minimumDistance(int distance[], Boolean spSet[]) { // Initialize min value int m = Integer.MAX_VALUE, m_index = -1; for (int vx = 0; vx <totalvertex; 0 1 3 4 5 6 9 vx++) { if (spset[vx]="=" false && distance[vx] <="m)" m="distance[vx];" m_index="vx;" } return m_index; a utility method to display the built distance array void printsolution(int distance[], int n) system.out.println('the shortest from source 0th node all other nodes are: '); for (int j="0;" n; j++) system.out.println('to ' + is: distance[j]); that does implementation of dijkstra's path algorithm graph is being represented using adjacency matrix representation dijkstra(int graph[][], s) distance[]="new" int[totalvertex]; output distance[i] holds s spset[j] will be true vertex included in tree or finalized boolean spset[]="new" boolean[totalvertex]; initializing distances as infinite and totalvertex; distance[j]="Integer.MAX_VALUE;" itself always distance[s]="0;" compute given vertices cnt="0;" totalvertex - 1; cnt++) choose minimum set not yet processed. ux equal first iteration. spset); choosed marked it means processed spset[ux]="true;" updating value neighboring vertex. vx="0;" update only spset, there an edge vx, total weight through lesser than current (!spset[vx] graph[ux][vx] !="-1" distance[ux] distance[vx]) graph[ux][vx]; build printsolution(distance, totalvertex); main public static main(string argvs[]) * created. arr[x][y]="-" means, no any connects x y directly grph[][]="new" int[][] -1, 3, 7, -1 }, 10, 6, 2, 8, 13, 9, 4, 1, 5, }; creating object class dijkstraexample obj="new" dijkstraexample(); obj.dijkstra(grph, 0); pre> <p> <strong>Output:</strong> </p> <pre> The shortest Distance from source 0th node to all other nodes are: To 0 the shortest distance is: 0 To 1 the shortest distance is: 3 To 2 the shortest distance is: 8 To 3 the shortest distance is: 10 To 4 the shortest distance is: 18 To 5 the shortest distance is: 10 To 6 the shortest distance is: 9 To 7 the shortest distance is: 7 To 8 the shortest distance is: 7 </pre> <p>The time complexity of the above code is O(V<sup>2</sup>), where V is the total number of vertices present in the graph. Such time complexity does not bother much when the graph is smaller but troubles a lot when the graph is of larger size. Therefore, we have to do the optimization to reduce this complexity. With the help of the priority queue, we can decrease the time complexity. Observe the following code that is written for the graph depicted above.</p> <p> <strong>FileName:</strong> DijkstraExample1.java</p> <pre> // Java Program shows the implementation Dijkstra&apos;s Algorithm // Using the Priority Queue // import statement import java.util.*; // Main class DijkstraExample1 public class DijkstraExample1 { // Member variables of the class private int distance[]; private Set settld; private PriorityQueue pQue; // Total count of the vertices private int totalNodes; List<list> adjacent; // Constructor of the class public DijkstraExample1(int totalNodes) { this.totalNodes = totalNodes; distance = new int[totalNodes]; settld = new HashSet(); pQue = new PriorityQueue(totalNodes, new Node()); } public void dijkstra(List<list> adjacent, int s) { this.adjacent = adjacent; for (int j = 0; j <totalnodes; j++) { initializing the distance of every node to infinity (a large number) distance[j]="Integer.MAX_VALUE;" } adding source pque pque.add(new node(s, 0)); is always zero distance[s]="0;" while (settld.size() !="totalNodes)" terminating condition check when priority queue contains elements, return if (pque.isempty()) return; deleting that has minimum from int ux="pQue.remove().n;" whose confirmed (settld.contains(ux)) continue; we don't have call eneighbors(ux) already present in settled set. settld.add(ux); eneighbours(ux); private void eneighbours(int ux) edgedist="-1;" newdist="-1;" all neighbors vx for (int j="0;" < adjacent.get(ux).size(); current hasn't been processed (!settld.contains(vx.n)) + edgedist; new lesser cost (newdist distance[vx.n]) distance[vx.n]="newDist;" node(vx.n, distance[vx.n])); main method public static main(string argvs[]) totalnodes="9;" s="0;" representation connected edges using adjacency list by declaration class object declaring and type list<list> adjacent = new ArrayList<list>(); // Initialize list for every node for (int i = 0; i <totalnodes; 0 1 2 3 i++) { list itm="new" arraylist(); adjacent.add(itm); } adding the edges statement adjacent.get(0).add(new node(1, 3)); means to travel from node 1, one has cover units of distance it does not mean 0, we have add adjacent.get(1).add(new node(0, note that is same i.e., in both cases. similarly, added other too. node(7, 7)); node(2, 10)); node(8, 4)); adjacent.get(2).add(new node(3, 6)); node(5, 2)); 1)); adjacent.get(3).add(new node(4, 8)); 13)); adjacent.get(4).add(new 9)); adjacent.get(5).add(new node(6, 5)); adjacent.get(6).add(new adjacent.get(7).add(new adjacent.get(8).add(new creating an object class dijkstraexample1 obj="new" dijkstraexample1(totalnodes); obj.dijkstra(adjacent, s); printing shortest path all nodes source system.out.println('the :'); for (int j="0;" < obj.distance.length; j++) system.out.println(s + ' obj.distance[j]); implementing comparator interface this represents a graph implements member variables public int n; price; constructors constructor node() node(int n, price) this.n="n;" this.price="price;" @override compare(node n1, n2) if (n1.price n2.price) return 1; 0; pre> <p> <strong>Output:</strong> </p> <pre> The shortest path from the node: 0 to 0 is 0 0 to 1 is 3 0 to 2 is 8 0 to 3 is 10 0 to 4 is 18 0 to 5 is 10 0 to 6 is 9 0 to 7 is 7 0 to 8 is 7 </pre> <p>The time complexity of the above implementation is O(V + E*log(V)), where V is the total number of vertices, and E is the number of Edges present in the graph.</p> <h2>Limitations of Dijkstra Algorithm</h2> <p>The following are some limitations of the Dijkstra Algorithm:</p> <ol class="points"> <li>The Dijkstra algorithm does not work when an edge has negative values.</li> <li>For cyclic graphs, the algorithm does not evaluate the shortest path. Hence, for the cyclic graphs, it is not recommended to use the Dijkstra Algorithm.</li> </ol> <h2>Usages of Dijkstra Algorithm</h2> <p>A few prominent usages of the Dijkstra algorithm are:</p> <ol class="points"> <li>The algorithm is used by Google maps.</li> <li>The algorithm is used to find the distance between two locations.</li> <li>In IP routing also, this algorithm is used to discover the shortest path.</li> </ol> <hr></totalnodes;></list></totalnodes;></list></list></pre></totalvertex;></pre></distance[ux]:>

Tidskomplexiteten för ovanstående kod är O(V²), där V är det totala antalet hörn som finns i grafen. Sådan tidskomplexitet stör inte mycket när grafen är mindre men stör mycket när grafen är av större storlek. Därför måste vi göra optimeringen för att minska denna komplexitet. Med hjälp av prioritetskön kan vi minska tidskomplexiteten. Observera följande kod som är skriven för grafen som avbildas ovan.

Filnamn: DijkstraExample1.java

 // Java Program shows the implementation Dijkstra&apos;s Algorithm // Using the Priority Queue // import statement import java.util.*; // Main class DijkstraExample1 public class DijkstraExample1 { // Member variables of the class private int distance[]; private Set settld; private PriorityQueue pQue; // Total count of the vertices private int totalNodes; List<list> adjacent; // Constructor of the class public DijkstraExample1(int totalNodes) { this.totalNodes = totalNodes; distance = new int[totalNodes]; settld = new HashSet(); pQue = new PriorityQueue(totalNodes, new Node()); } public void dijkstra(List<list> adjacent, int s) { this.adjacent = adjacent; for (int j = 0; j <totalnodes; j++) { initializing the distance of every node to infinity (a large number) distance[j]="Integer.MAX_VALUE;" } adding source pque pque.add(new node(s, 0)); is always zero distance[s]="0;" while (settld.size() !="totalNodes)" terminating condition check when priority queue contains elements, return if (pque.isempty()) return; deleting that has minimum from int ux="pQue.remove().n;" whose confirmed (settld.contains(ux)) continue; we don\'t have call eneighbors(ux) already present in settled set. settld.add(ux); eneighbours(ux); private void eneighbours(int ux) edgedist="-1;" newdist="-1;" all neighbors vx for (int j="0;" < adjacent.get(ux).size(); current hasn\'t been processed (!settld.contains(vx.n)) + edgedist; new lesser cost (newdist distance[vx.n]) distance[vx.n]="newDist;" node(vx.n, distance[vx.n])); main method public static main(string argvs[]) totalnodes="9;" s="0;" representation connected edges using adjacency list by declaration class object declaring and type list<list> adjacent = new ArrayList<list>(); // Initialize list for every node for (int i = 0; i <totalnodes; 0 1 2 3 i++) { list itm="new" arraylist(); adjacent.add(itm); } adding the edges statement adjacent.get(0).add(new node(1, 3)); means to travel from node 1, one has cover units of distance it does not mean 0, we have add adjacent.get(1).add(new node(0, note that is same i.e., in both cases. similarly, added other too. node(7, 7)); node(2, 10)); node(8, 4)); adjacent.get(2).add(new node(3, 6)); node(5, 2)); 1)); adjacent.get(3).add(new node(4, 8)); 13)); adjacent.get(4).add(new 9)); adjacent.get(5).add(new node(6, 5)); adjacent.get(6).add(new adjacent.get(7).add(new adjacent.get(8).add(new creating an object class dijkstraexample1 obj="new" dijkstraexample1(totalnodes); obj.dijkstra(adjacent, s); printing shortest path all nodes source system.out.println(\'the :\'); for (int j="0;" < obj.distance.length; j++) system.out.println(s + \' obj.distance[j]); implementing comparator interface this represents a graph implements member variables public int n; price; constructors constructor node() node(int n, price) this.n="n;" this.price="price;" @override compare(node n1, n2) if (n1.price n2.price) return 1; 0; pre> <p> <strong>Output:</strong> </p> <pre> The shortest path from the node: 0 to 0 is 0 0 to 1 is 3 0 to 2 is 8 0 to 3 is 10 0 to 4 is 18 0 to 5 is 10 0 to 6 is 9 0 to 7 is 7 0 to 8 is 7 </pre> <p>The time complexity of the above implementation is O(V + E*log(V)), where V is the total number of vertices, and E is the number of Edges present in the graph.</p> <h2>Limitations of Dijkstra Algorithm</h2> <p>The following are some limitations of the Dijkstra Algorithm:</p> <ol class="points"> <li>The Dijkstra algorithm does not work when an edge has negative values.</li> <li>For cyclic graphs, the algorithm does not evaluate the shortest path. Hence, for the cyclic graphs, it is not recommended to use the Dijkstra Algorithm.</li> </ol> <h2>Usages of Dijkstra Algorithm</h2> <p>A few prominent usages of the Dijkstra algorithm are:</p> <ol class="points"> <li>The algorithm is used by Google maps.</li> <li>The algorithm is used to find the distance between two locations.</li> <li>In IP routing also, this algorithm is used to discover the shortest path.</li> </ol> <hr></totalnodes;></list></totalnodes;></list></list>

Tidskomplexiteten för implementeringen ovan är O(V + E*log(V)), där V är det totala antalet hörn och E är antalet kanter som finns i grafen.

Begränsningar för Dijkstra Algorithm

Följande är några begränsningar för Dijkstra-algoritmen:

Dijkstra-algoritmen fungerar inte när en kant har negativa värden.
För cykliska grafer utvärderar inte algoritmen den kortaste vägen. Därför, för de cykliska graferna, rekommenderas det inte att använda Dijkstra-algoritmen.

Användning av Dijkstra Algorithm

Några framträdande användningar av Dijkstra-algoritmen är:

Algoritmen används av Google maps.
Algoritmen används för att hitta avståndet mellan två platser.
Även i IP-routing används denna algoritm för att upptäcka den kortaste vägen.