how implement dijkstra s algorithm java
このチュートリアルでは、例を使用して、ダイクストラのアルゴリズムをJavaに実装し、グラフまたはツリーで最短ルートを見つける方法について説明します。
Javaのグラフに関する以前のチュートリアルでは、グラフを使用して、他のアプリケーションとは別にノード間の最短パスを見つけることを確認しました。
グラフの2つのノード間の最短経路を見つけるために、主に「」と呼ばれるアルゴリズムを使用します。 ダイクストラのアルゴリズム 」。このアルゴリズムは、グラフまたはツリー内の最短ルートを見つけるために広く使用されているアルゴリズムのままです。
=> ここですべてのJavaチュートリアルを確認してください
学習内容：
Javaでのダイクストラのアルゴリズム
重み付きグラフとグラフの開始（ソース）頂点が与えられると、ダイクストラのアルゴリズムを使用して、ソースノードからグラフ内の他のすべてのノードまでの最短距離を見つけます。
グラフ上でダイクストラのアルゴリズムを実行した結果、ソース頂点をルートとして最短パスツリー（SPT）を取得します。
ダイクストラのアルゴリズムでは、2つのセットまたはリストを維持します。 1つには、最短パスツリー（SPT）の一部である頂点が含まれ、もう1つには、SPTに含まれると評価されている頂点が含まれます。したがって、反復ごとに、最短パスを持つ2番目のリストから頂点を見つけます。
ダイクストラの最短経路アルゴリズムの擬似コードを以下に示します。
ワイヤレスルーターのセキュリティキーは何ですか
擬似コード
以下に、このアルゴリズムの擬似コードを示します。
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 サンプルグラフを見て、ダイクストラの最短経路アルゴリズムを説明しましょう 。
最初は、SPT（Shortest Path Tree）セットが無限大に設定されています。
頂点0から始めましょう。まず、頂点0をsptSetに配置します。
sptSet = {0、INF、INF、INF、INF、INF}。
次に、sptSetの頂点0を使用して、その近傍を探索します。頂点1と2は、それぞれ距離2と1の0の2つの隣接するノードです。
上の図では、隣接する各頂点（1と2）を、ソース頂点0からのそれぞれの距離で更新しています。これで、頂点2の距離が最小であることがわかります。次に、頂点2をsptSetに追加します。また、頂点2の近傍を探索します。
ここで、最小距離の頂点と、sptにない頂点を探します。距離2の頂点1を選択します。
上の図に示されているように、2、0、および1のすべての隣接ノードのうち、すでにsptSetにあるため、それらを無視します。隣接するノード5と3のうち、5のコストが最も低くなります。そこで、それをsptSetに追加し、隣接するノードを探索します。
上の図では、ノード3と4を除いて、他のすべてのノードがsptSetにあることがわかります。 3と4のうち、ノード3のコストが最も低くなります。そこで、sptSetに入れます。
上に示したように、頂点は1つだけ残っています。つまり4で、ルートノードからの距離は16です。最後に、それをsptSetに入れて、最終的なsptSet = {0、2、1、5、3、4}を取得します。ソースノード0からの各頂点の距離を示します。
Javaでのダイクストラのアルゴリズムの実装
Javaでのダイクストラの最短経路アルゴリズムの実装は、2つの方法を使用して実現できます。優先キューと隣接リストを使用することも、隣接行列と配列を使用することもできます。
このセクションでは、両方の実装について説明します。
優先キューの使用
この実装では、優先度キューを使用して、最短距離の頂点を格納します。グラフは隣接リストを使用して定義されます。サンプルプログラムを以下に示します。
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 出力：
隣接行列の使用
このアプローチでは、隣接行列を使用してグラフを表します。 sptセットには、配列を使用します。
次のプログラムは、この実装を示しています。
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 出力：
よくある質問
Q＃1）ダイクストラは無向グラフで機能しますか？
回答： ダイクストラのアルゴリズムの場合、グラフが有向であるか無向であるかは問題ではありません。このアルゴリズムは、グラフの頂点と重みのみに関係します。
Q＃2）ダイクストラのアルゴリズムの時間計算量はどれくらいですか？
回答： ダイクストラのアルゴリズムの時間計算量はO（V 2）です。 min-priorityキューを使用して実装すると、このアルゴリズムの時間計算量はO（V + E l o g V）になります。
Q＃3）ダイクストラは欲張りアルゴリズムですか？
回答： はい、ダイクストラは欲張りアルゴリズムです。最小スパニングツリー（MST）を見つけるPrimのアルゴリズムと同様に、これらのアルゴリズムもルート頂点から開始し、常に最小パスで最適な頂点を選択します。
Q＃4）ダイクストラDFSまたはBFSですか？
回答： どちらでもありません。ただし、ダイクストラのアルゴリズムは実装に優先度付きキューを使用するため、BFSに近いと見なすことができます。
Q＃5）ダイクストラアルゴリズムはどこで使用されていますか？
回答： あるノードから別のノードへの最短パスを見つけるのに役立つため、主にルーティングプロトコルで使用されます。
結論
このチュートリアルでは、ダイクストラのアルゴリズムについて説明しました。このアルゴリズムを使用して、ルートノードからグラフまたはツリー内の他のノードへの最短パスを見つけます。
最小パスを見つける必要があるため、通常、優先度キューを使用してダイクストラのアルゴリズムを実装します。隣接行列を使用してこのアルゴリズムを実装することもできます。このチュートリアルでは、これら両方のアプローチについて説明しました。
このチュートリアルがお役に立てば幸いです。
=> すべてのJavaトレーニングシリーズを見るには、ここにアクセスしてください
推奨読書
