logo

TechCodeview

Dijkstra'nın Algoritması Java

Dijkstra algoritması Kaynak düğümden hedef düğüme en kısa yolu bulmak için öne çıkan algoritmalardan biri. En kısa yolu bulmak için açgözlü yaklaşımı kullanır. Dijkstra algoritmasının konsepti kaynak noktadan başlayarak en kısa mesafeyi (yolu) bulmak ve güncelleme yaparken daha uzun mesafeleri göz ardı etmektir.

Bu bölümde uygulayacağımız Java programında Dijkstra algoritması . Ayrıca kullanımını ve sınırlamalarını tartışacağız.

Dijkstra Algoritmasının Adımları

Aşama 1: Tüm düğümler ziyaret edilmemiş olarak işaretlenmelidir.

Adım 2: Tüm düğümlerin 'sonsuz' (büyük bir sayı) mesafeyle başlatılması gerekir. Başlangıç ​​düğümü sıfırla başlatılmalıdır.

Aşama 3: Başlangıç ​​düğümünü geçerli düğüm olarak işaretleyin.

Adım4: Mevcut düğümden, henüz ziyaret edilmemiş tüm komşularını analiz edin ve mevcut düğüm ile komşu düğüm arasındaki bağlantıyı kuran kenarın ağırlığını mevcut düğümün mevcut mesafesine ekleyerek mesafelerini hesaplayın.

Adım 5: Şimdi, yakın zamanda hesaplanan mesafeyi komşu düğüme ayrılan mesafeyle karşılaştırın ve bunu komşu düğümün mevcut mesafesi olarak kabul edin,

Adım6: Daha sonra mevcut düğümün ziyaret edilmemiş çevre komşuları dikkate alınır ve mevcut düğümler ziyaret edilmiş olarak işaretlenir.

Adım 7: Bitiş düğümü ziyaret edildi olarak işaretlendiğinde algoritma işini yapmış demektir; aksi takdirde,

Adım 8: Minimum mesafeye ayrılmış, ziyaret edilmemiş düğümü seçin ve onu yeni mevcut düğüm olarak değerlendirin. Bundan sonra 4. adımdan tekrar başlayın.

Dijkstra Algoritması Sözde Kodu

 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]:>

Yukarıdaki kodun zaman karmaşıklığı O(V)2), burada V, grafikte bulunan toplam köşe sayısıdır. Bu tür zaman karmaşıklığı, grafik küçük olduğunda pek sorun yaratmaz, ancak grafik boyutu büyük olduğunda çok sorun yaratır. Dolayısıyla bu karmaşıklığı azaltmak için optimizasyon yapmamız gerekiyor. Öncelik kuyruğunun yardımıyla zaman karmaşıklığını azaltabiliriz. Yukarıda gösterilen grafik için yazılan aşağıdaki kodu inceleyin.

Dosya adı: DijkstraÖrnek1.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>

Yukarıdaki uygulamanın zaman karmaşıklığı O(V + E*log(V)) şeklindedir; burada V, toplam köşe sayısıdır ve E, grafikte bulunan Kenarların sayısıdır.

Dijkstra Algoritmasının Sınırlamaları

Dijkstra Algoritmasının bazı sınırlamaları şunlardır:

  1. Dijkstra algoritması, bir kenarın negatif değerleri olduğunda çalışmaz.
  2. Döngüsel grafikler için algoritma en kısa yolu değerlendirmez. Bu nedenle döngüsel grafikler için Dijkstra Algoritmasının kullanılması önerilmez.

Dijkstra Algoritmasının Kullanım Alanları

Dijkstra algoritmasının öne çıkan birkaç kullanımı şunlardır:

  1. Algoritma Google haritaları tarafından kullanılıyor.
  2. Algoritma iki konum arasındaki mesafeyi bulmak için kullanılır.
  3. IP yönlendirmede de bu algoritma en kısa yolu bulmak için kullanılır.