Javaで隣接リストを使用したダイクストラのアルゴリズムの実装方法

まず、隣接リストを作成する必要があります。隣接リストは、各頂点に隣接する頂点のリストを持つデータ構造です。以下のように、各頂点を表すVertexクラスと、グラフを表すGraphクラスを作成します。

import java.util.*;
class Vertex {
    int id;
    List<Edge> edges;
    public Vertex(int id) {
        this.id = id;
        this.edges = new ArrayList<>();
    }
    public void addEdge(Edge edge) {
        edges.add(edge);
    }
}
class Edge {
    Vertex target;
    int weight;
    public Edge(Vertex target, int weight) {
        this.target = target;
        this.weight = weight;
    }
}
class Graph {
    List<Vertex> vertices;
    public Graph() {
        this.vertices = new ArrayList<>();
    }
    public void addVertex(Vertex vertex) {
        vertices.add(vertex);
    }
}

次に、ダイクストラのアルゴリズムを実装します。以下のように、ダイクストラクラスを作成し、dijkstraメソッドを実装します。

import java.util.*;
class Dijkstra {
    public static void dijkstra(Graph graph, Vertex source) {
        Map<Vertex, Integer> distances = new HashMap<>();
        Map<Vertex, Vertex> previous = new HashMap<>();
        PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(distances::get));
        for (Vertex vertex : graph.vertices) {
            distances.put(vertex, Integer.MAX_VALUE);
            previous.put(vertex, null);
        }
        distances.put(source, 0);
        queue.offer(source);
        while (!queue.isEmpty()) {
            Vertex current = queue.poll();
            for (Edge edge : current.edges) {
                int newDistance = distances.get(current) + edge.weight;
                if (newDistance < distances.get(edge.target)) {
                    distances.put(edge.target, newDistance);
                    previous.put(edge.target, current);
                    queue.offer(edge.target);
                }
            }
        }
// 結果を出力
        for (Vertex vertex : graph.vertices) {
            System.out.println("頂点 " + vertex.id + " までの最短距離: " + distances.get(vertex));
            List<Vertex> path = new ArrayList<>();
            Vertex current = vertex;
            while (current != null) {
                path.add(current);
                current = previous.get(current);
            }
            Collections.reverse(path);
            System.out.println("最短経路: " + path);
        }
    }
}

最後に、メインメソッドを作成し、グラフと開始頂点を作成し、ダイクストラのアルゴリズムを呼び出します。

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        Vertex v1 = new Vertex(1);
        Vertex v2 = new Vertex(2);
        Vertex v3 = new Vertex(3);
        Vertex v4 = new Vertex(4);
        v1.addEdge(new Edge(v2, 5));
        v1.addEdge(new Edge(v3, 2));
        v2.addEdge(new Edge(v3, 1));
        v2.addEdge(new Edge(v4, 6));
        v3.addEdge(new Edge(v4, 3));
        graph.addVertex(v1);
        graph.addVertex(v2);
        graph.addVertex(v3);
        graph.addVertex(v4);
        Dijkstra.dijkstra(graph, v1);
    }
}

このコードでは、与えられたグラフ内の各頂点までの最短距離と最短経路を計算し、結果を出力します。上記の例では、グラフが以下のように定義されています。

       5       6
   (1)---►(2)---►(4)
    |     / ↑     / ↑
    |    /  |    /  |
   2|   1  3|   3  |
    |  /    |  /    |
   (3)---►(4)◄---|

最終的な出力は次のようになります。

頂点 1 までの最短距離: 0
最短経路: [1]
頂点 2 までの最短距離: 3
最短経路: [1, 3, 2]
頂点 3 までの最短距離: 2
最短経路: [1, 3]
頂点 4 までの最短距離: 5
最短経路: [1, 3, 4]

このようにして、Javaで隣接リストを使用してダイクストラのアルゴリズムを実装することができます。