Dijkstra algoritam je jedan od istaknutih algoritama za pronalaženje najkraćeg puta od izvornog čvora do odredišnog čvora. Koristi se pohlepnim pristupom kako bi pronašao najkraći put. Koncept Dijkstra algoritma je pronaći najkraću udaljenost (put) počevši od izvorne točke i zanemariti veće udaljenosti tijekom ažuriranja.
U ovom odjeljku ćemo implementirati Dijkstra algoritam u Java programu . Također, razgovarat ćemo o njegovoj upotrebi i ograničenjima.
Koraci Dijkstra algoritma
Korak 1: Svi čvorovi trebaju biti označeni kao neposjećeni.
Korak 2: Svi čvorovi moraju biti inicijalizirani s 'beskonačnom' (velikim brojem) udaljenosti. Početni čvor mora biti inicijaliziran s nulom.
3. korak: Označite početni čvor kao trenutni čvor.
Korak 4: Iz trenutnog čvora analizirajte sve njegove susjede koji još nisu posjećeni i izračunajte njihove udaljenosti dodavanjem težine ruba, čime se uspostavlja veza između trenutnog čvora i susjednog čvora na trenutnu udaljenost trenutnog čvora.
Korak 5: Sada usporedite nedavno izračunatu udaljenost s udaljenošću dodijeljenom susjednom čvoru i tretirajte je kao trenutnu udaljenost susjednog čvora,
Korak 6: Nakon toga se razmatraju okolni susjedi trenutnog čvora koji nije posjećen, a trenutni čvorovi se označavaju kao posjećeni.
Korak 7: Kada je završni čvor označen kao posjećen, tada je algoritam obavio svoj posao; inače,
Korak 8: Odaberite neposjećeni čvor kojem je dodijeljena minimalna udaljenost i tretirajte ga kao novi trenutni čvor. Nakon toga, počnite ponovno od koraka 4.
Pseudo kod Dijkstra algoritma
Method Dijkstra(G, s): // G is graph, s is source distance[s] -> 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] -> 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'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'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]:> Vremenska složenost gornjeg koda je O(V2), gdje je V ukupan broj vrhova prisutnih u grafu. Takva vremenska složenost ne smeta puno kada je graf manji, ali mnogo smeta kada je graf veće veličine. Stoga moramo izvršiti optimizaciju kako bismo smanjili ovu složenost. Uz pomoć reda prioriteta možemo smanjiti vremensku složenost. Obratite pozornost na sljedeći kod koji je napisan za gore prikazani grafikon.
np gdje
Naziv datoteke: DijkstraExample1.java
// Java Program shows the implementation Dijkstra'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> Vremenska složenost gornje implementacije je O(V + E*log(V)), gdje je V ukupan broj vrhova, a E broj bridova prisutnih u grafu.
Ograničenja Dijkstra algoritma
Slijede neka ograničenja Dijkstra algoritma:
- Dijkstra algoritam ne radi kada rub ima negativne vrijednosti.
- Za cikličke grafove, algoritam ne procjenjuje najkraći put. Stoga se za cikličke grafove ne preporučuje korištenje Dijkstra algoritma.
Upotreba Dijkstra algoritma
Nekoliko istaknutih upotreba Dijkstra algoritma su:
- Algoritam koriste Google karte.
- Algoritam se koristi za pronalaženje udaljenosti između dvije lokacije.
- U IP usmjeravanju također se ovaj algoritam koristi za otkrivanje najkraćeg puta.