ダイクストラアルゴリズムは 送信元ノードから宛先ノードまでの最短パスを見つけるための著名なアルゴリズムの 1 つ。貪欲なアプローチを使用して最短パスを見つけます。ダイクストラ アルゴリズムの概念は、ソース ポイントから始まる最短距離 (パス) を見つけ、更新中に長い距離を無視することです。
このセクションでは、 Javaプログラムのダイクストラアルゴリズム 。また、その使用法と制限事項についても説明します。
ダイクストラアルゴリズムのステップ
ステップ1： すべてのノードは未訪問としてマークされる必要があります。
ステップ2： すべてのノードは「無限」(大きな数) の距離を使用して初期化する必要があります。開始ノードはゼロで初期化する必要があります。
ステップ3: 開始ノードを現在のノードとしてマークします。
ステップ4: 現在のノードから、まだ訪問されていないすべての隣接ノードを分析し、現在のノードと隣接ノードの間の接続を確立するエッジの重みを現在のノードの現在の距離に追加することによってそれらの距離を計算します。
ステップ5: ここで、最近計算された距離と隣接ノードに割り当てられた距離を比較し、それを隣接ノードの現在の距離として扱います。
ステップ6: その後、訪問されていない現在のノードの周囲の隣接ノードが考慮され、現在のノードは訪問済みとしてマークされます。
ステップ7: 終了ノードが訪問済みとしてマークされると、アルゴリズムはその仕事を完了したことになります。さもないと、
ステップ8: 最小距離が割り当てられている未訪問のノードを選択し、それを新しい現在のノードとして扱います。その後、再度手順4からやり直してください。
ダイクストラアルゴリズムの擬似コード
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]:> 上記のコードの時間計算量は O(V2)、ここで、V はグラフ内に存在する頂点の総数です。このような時間計算量は、グラフが小さい場合にはそれほど問題になりませんが、グラフのサイズが大きくなると非常に問題になります。したがって、この複雑さを軽減するために最適化を行う必要があります。プライオリティ キューの助けを借りて、時間の複雑さを軽減できます。上に示したグラフ用に記述された次のコードに注目してください。
ファイル名： 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> 上記の実装の時間計算量は O(V + E*log(V)) です。ここで、V は頂点の総数、E はグラフ内に存在するエッジの数です。
ダイクストラアルゴリズムの制限
ダイクストラ アルゴリズムには次のような制限があります。
- エッジに負の値がある場合、ダイクストラ アルゴリズムは機能しません。
- 循環グラフの場合、アルゴリズムは最短パスを評価しません。したがって、循環グラフでは、ダイクストラ アルゴリズムを使用することはお勧めできません。
ダイクストラアルゴリズムの使用法
ダイクストラ アルゴリズムの主な使用例をいくつか示します。
- このアルゴリズムは Google マップで使用されています。
- このアルゴリズムは、2 つの位置間の距離を見つけるために使用されます。
- IP ルーティングでも、このアルゴリズムは最短パスを発見するために使用されます。