ダイクストラ法の実装

はじめに

この実験では、Java でダイクストラ法を実装します。ダイクストラ法は、重み付きグラフの最短経路問題を解くために使われる一般的なアルゴリズムです。

グラフクラスを作成する

このステップでは、重み付きグラフを表す Graph というクラスを作成します。このクラスでは、グラフの辺を表す 2 次元の隣接行列を作成します。

class Graph
{
    int[][] adjMatrix; // 辺を表す隣接行列
    int numOfvertices;

    Graph(int[][] mat, int v)
    {
        this.adjMatrix = mat;
        this.numOfvertices = v;
    }

    void addEdge(int src, int dest, int edgeWeight)
    {
        adjMatrix[src][dest] = edgeWeight;
        adjMatrix[dest][src] = edgeWeight;
    }
}

ダイクストラ法を実装する

このステップでは、Java でダイクストラ法を実装します。最も近い未訪問ノードを見つけるための getClosestVertex というヘルパーメソッドを作成します。また、dijkstrasShortestPath メソッドでメインアルゴリズムも実装します。このメソッドは、Graph とソースノードをパラメータとして受け取り、最短距離配列を返します。

public static int getClosestVertex(int[] distance, boolean[] visited) {
    int min = Integer.MAX_VALUE;
    int minIdx = -1;
    for(int i=0; i<distance.length; i++) {
        if(distance[i] < min)
            if(visited[i] == false) {
                min = distance[i];
                minIdx = i;
            }
    }
    return minIdx;
}

public static int[] dijkstrasShortestPath(Graph g, int src) {
    // 最終的な最短距離配列
    int[] distance = new int[g.numOfvertices];
    // ノードの最短距離が見つかったかどうかを示す配列
    boolean[] visited = new boolean[g.numOfvertices];

    // 配列の初期化
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // 初期距離は無限大
        visited[i] = false; // 任意のノードの最短距離がまだ見つかっていない
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // 最も近いノードを取得
        if(closestVertex == Integer.MAX_VALUE) // 最も近いノードが無限距離であれば、他のノードに到達できないことを意味する。したがって返す
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // ノード j の最短距離が確定していない場合
            {
                if(g.adjMatrix[closestVertex][j]!= 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // 最も近いノードを経由する距離が初期距離より小さい場合
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

私たちの実装をテストする

このステップでは、メインメソッドを作成して実装をテストします。このメインメソッドでは、グラフに辺を追加し、重み付きグラフのソースノードから他のすべてのノードまでの最短距離を求めるために、dijkstrasShortestPath メソッドを呼び出します。

public static void main(String[] args) {
    int numOfVertices = 6;
    int[][] adjMat = new int[6][6];
    Graph graph = new Graph(adjMat, numOfVertices);

    // グラフに辺を追加する
    graph.addEdge(0, 4, 21);
    graph.addEdge(0, 3, 18);
    graph.addEdge(2, 1, 7);
    graph.addEdge(1, 4, 6);
    graph.addEdge(4, 5, 10);
    graph.addEdge(4, 3, 11);
    graph.addEdge(5, 3, 7);

    // 最短距離を求めるためにダイクストラ法を呼び出す
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

上記のコードをコンパイルして実行すると、最短距離配列 [0, 27, 34, 18, 21, 25] が得られます。

まとめ

おめでとうございます！あなたはダイクストラ法の実装の実験を完了しました。あなたの技術を向上させるために、LabEx でさらに多くの実験を行って練習してください。