この記事では、Java に基づくダイクストラ アルゴリズムを例の形式で紹介します。読者がデータ構造ドメイン アルゴリズムを学習する際に役立つと思います。
ダイクストラは、各頂点とソース点 v の間の経路長が大きい順に各頂点への最短経路を生成するアルゴリズムを提案しました。つまり、最初に最も長さが短い最短パスを検索し、次にそれを使用して次に長さが短い最短パスを検索し、ソース点 v から他の頂点までのすべての最短パスが見つかるまでこれを繰り返します。
コードの実装は次のとおりです。
package com.algorithm.impl; public class Dijkstra { private static int M = 10000; //この道路は通行止めです public static void main(String[] args) { int[][] Weight1 = {//隣接行列 {0, 3 ,2000,7,M}、{3,0,4,2,M}、{M,4,0,5,4}、{7,2,5,0,6}、 {M,M,4,6,0} }; int[][] 重み 2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; int start=0; int[] dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("「+start+」から「+i+」までの最短距離は次のとおりです: "+shortPath[i ] ); } パブリック静的 int[] dijkstra(int[][] 重み, int 開始) { //有向グラフの重み行列と開始点番号 start (0 から番号が付けられ、頂点は配列に格納されます) を受け取ります //start からそこまでの最短パスの長さを示す int[] 配列を返しますint n =weight.length ; //頂点の数 int[] shortPath = new int[n] //開始点から他の点までの最短パスを保存 String[] path = new String[n];始点から他の点までのパス 文字列表現 for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] Visited = new int[n]; // 現在の頂点への最短パスかどうかをマークします。 has been Find、1 は見つかったことを意味します //初期化、最初の頂点が見つかったことを意味します shortPath[start] = 0; visit[start] = 1; for(int count = 1; count < n; count++) { //n-1 個の頂点を追加するには int k = -1; //最初の頂点 start に最も近いマークされていない頂点を選択します int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited) [i] == 0 && 重み[開始][i] < dmin) { dmin = 重み[開始] [i] } } // 新しく選択した頂点を最短パスが見つかったとしてマークし、開始する最短パスは dmin shortPath[k] = dmin; // k を中間点として、パスを修正します。 start から未訪問点までの距離 for(int i = 0; i < n; i++) { if(visited[i] == 0 &&weight[start][k] +weight[k][i] <weight[start] [私]） {重み[開始][i] = 重み[開始][k] + 重み[k][i]; パス[i] = パス[k] + "-->" + i; 0; i < n; i++) { System.out.println("「+start+」から「+i+」への最短パスは次のとおりです: "+path[i]); System.out.println("======================================); return shortPath; }}このプログラムを実行した結果は次のようになります。
0 から 0 への最短パスは 0-->0 0 から 1 への最短パスは 0-->1 0 から 2 への最短パスは 0-->3-->2 から0 から 3 までは: 0-->3 0 から 4 までの最短パスは: 0-->3-->2-->4==== =================================0 から 0 までの最短距離は次のとおりです。 0 0 から 1 までの最短距離0 から 2 までの距離は 50 0 から 3 までの最短距離は 30 0 から 4 までの最短距離は 60