Javaでのダイクストラ最短経路アルゴリズム

1. 概要

この記事で強調しているのは、グラフ理論で知られている基本的な理論上の問題の1つである最短経路問題（SPP）と、ダイクストラアルゴリズムを使用してそれを解決する方法です。

アルゴリズムの基本的な目標は、開始ノードとグラフの残りの部分との間の最短経路を決定することです。

2. Dijkstraの最短経路問題

正の 加重グラフ と開始ノード (A) が与えられた場合、ダイクストラはソースからグラフ内のすべての目的地までの最短経路と距離を決定します。

ダイクストラアルゴリズムの中心的な考え方は、開始ノードとすべての可能な宛先の間のより長いパスを継続的に排除することです。

プロセスを追跡するには、決済済みと未決済の2つの異なるノードのセットが必要です。

解決されたノードは、ソースからの最小距離がわかっているノードです。 Unsettled nodes set は、ソースから到達できるノードを集めますが、開始ノードからの最小距離はわかりません。

ダイクストラで SPP を解決するために従うべき手順のリストを次に示します。

• startNodeまでの距離をゼロに設定します。
• 他のすべての距離を無限の値に設定します。
• startNodeを未決済のノードセットに追加します。
• 未決済のノードセットは空ではありませんが、次のようにします。
  • 未決済のノードセットから評価ノードを選択します。評価ノードは、ソースからの距離が最も短いノードである必要があります。
  • 各評価で最短距離を維持することにより、直接隣接する距離までの新しい距離を計算します。
  • まだ解決されていないネイバーを未解決のノードセットに追加します。

これらのステップは、初期化と評価の2つの段階に集約できます。 これがサンプル グラフにどのように適用されるか見てみましょう。

2.1. 初期化

グラフ内のすべてのパスの探索を開始する前に、まず、ソースを除いて、無限の距離と未知の先行ノードを持つすべてのノードを初期化する必要があります。

初期化プロセスの一環として、ノードAに値0を割り当てる必要があります（ノードAからノードAまでの距離は明らかに0であることがわかっています）。

したがって、グラフの残りの各ノードは、先行ノードと距離で区別されます。

初期化プロセスを完了するには、ノードAを未決済のノードに追加して、評価ステップで最初に選択されるように設定する必要があります。 解決されたノードセットはまだ空であることに注意してください。

2.2. 評価

グラフが初期化されたので、未解決のセットからの距離が最も短いノードを選択し、次に、解決済みのノードにないすべての隣接ノードを評価します。

アイデアは、エッジの重みを評価ノードの距離に追加し、それを宛先の距離と比較することです。 例えば ノードBの場合、0 + 10はINFINITYよりも小さいため、ノードBの新しい距離は10であり、新しい先行ノードはAであり、同じことがノードCにも当てはまります。

次に、ノードAは、未決済のノードセットから決済済みのノードに移動されます。

ノードBとCは、到達可能であるため、未解決のノードに追加されますが、評価する必要があります。

未決済のセットに2つのノードがあるので、距離が最も短いノード（ノードB）を選択し、グラフ内のすべてのノードを決済するまで繰り返します。

次の表は、評価ステップで実行された反復をまとめたものです。

たとえば、表記B-22は、ノードBが直前のノードであり、ノードAからの合計距離が22であることを意味します。

最後に、ノードAからの最短経路を次のように計算できます。

• ノードB：A –> B（合計距離= 10）
• ノードC：A –> C（合計距離= 15）
• ノードD：A –> B –> D（合計距離= 22）
• ノードE：A –> B –> D –> E（合計距離= 24）
• ノードF：A –> B –> D –> F（合計距離= 23）

3. Javaの実装

この単純な実装では、グラフをノードのセットとして表します。

public class Graph {

    private Set<Node> nodes = new HashSet<>();
    
    public void addNode(Node nodeA) {
        nodes.add(nodeA);
    }

    // getters and setters 
}Copy

ノードは、 name 、 LinkedList を参照して、 shortestPath 、ソースからの距離、および隣接関係で記述できます。 adjacentNodes という名前のリスト：

public class Node {
    
    private String name;
    
    private List<Node> shortestPath = new LinkedList<>();
    
    private Integer distance = Integer.MAX_VALUE;
    
    Map<Node, Integer> adjacentNodes = new HashMap<>();

    public void addDestination(Node destination, int distance) {
        adjacentNodes.put(destination, distance);
    }
 
    public Node(String name) {
        this.name = name;
    }
    
    // getters and setters
}Copy

adjacentNodes 属性は、隣接ノードをエッジ長に関連付けるために使用されます。 これは隣接リストの簡略化された実装であり、隣接行列よりもダイクストラアルゴリズムに適しています。

shortestPath 属性は、開始ノードから計算された最短経路を表すノードのリストです。

デフォルトでは、すべてのノード距離は Integer.MAX_VALUE で初期化され、初期化手順で説明されているように無限距離をシミュレートします。

それでは、ダイクストラ アルゴリズムを実装しましょう。

public static Graph calculateShortestPathFromSource(Graph graph, Node source) {
    source.setDistance(0);

    Set<Node> settledNodes = new HashSet<>();
    Set<Node> unsettledNodes = new HashSet<>();

    unsettledNodes.add(source);

    while (unsettledNodes.size() != 0) {
        Node currentNode = getLowestDistanceNode(unsettledNodes);
        unsettledNodes.remove(currentNode);
        for (Entry < Node, Integer> adjacencyPair: 
          currentNode.getAdjacentNodes().entrySet()) {
            Node adjacentNode = adjacencyPair.getKey();
            Integer edgeWeight = adjacencyPair.getValue();
            if (!settledNodes.contains(adjacentNode)) {
                calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
                unsettledNodes.add(adjacentNode);
            }
        }
        settledNodes.add(currentNode);
    }
    return graph;
}Copy

getLowestDistanceNode（）メソッドは、未解決のノードセットからの距離が最も短いノードを返します。calculateMinimumDistance（）メソッドは、新しく計算された距離を追跡しながら、実際の距離を新しく計算された距離と比較します。探索されたパス：

private static Node getLowestDistanceNode(Set < Node > unsettledNodes) {
    Node lowestDistanceNode = null;
    int lowestDistance = Integer.MAX_VALUE;
    for (Node node: unsettledNodes) {
        int nodeDistance = node.getDistance();
        if (nodeDistance < lowestDistance) {
            lowestDistance = nodeDistance;
            lowestDistanceNode = node;
        }
    }
    return lowestDistanceNode;
}Copy

private static void CalculateMinimumDistance(Node evaluationNode,
  Integer edgeWeigh, Node sourceNode) {
    Integer sourceDistance = sourceNode.getDistance();
    if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) {
        evaluationNode.setDistance(sourceDistance + edgeWeigh);
        LinkedList<Node> shortestPath = new LinkedList<>(sourceNode.getShortestPath());
        shortestPath.add(sourceNode);
        evaluationNode.setShortestPath(shortestPath);
    }
}Copy

必要な部分がすべて揃ったので、記事の主題であるサンプル グラフにダイクストラ アルゴリズムを適用しましょう。

Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D"); 
Node nodeE = new Node("E");
Node nodeF = new Node("F");

nodeA.addDestination(nodeB, 10);
nodeA.addDestination(nodeC, 15);

nodeB.addDestination(nodeD, 12);
nodeB.addDestination(nodeF, 15);

nodeC.addDestination(nodeE, 10);

nodeD.addDestination(nodeE, 2);
nodeD.addDestination(nodeF, 1);

nodeF.addDestination(nodeE, 5);

Graph graph = new Graph();

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);
graph.addNode(nodeE);
graph.addNode(nodeF);

graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA);
Copy

計算後、shortestPathおよびdistance属性がグラフの各ノードに設定され、それらを反復処理して、結果が前のセクションで見つかったものと正確に一致することを確認できます。

4. 結論

この記事では、ダイクストラ アルゴリズムが SPP を解決する方法と、Java でそれを実装する方法を見てきました。

この単純なプロジェクトの実装は、次のGitHubプロジェクトリンクにあります。