1概要

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

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


2ダイクストラによる最短経路問題

正の加重グラフと開始ノード(A)が与えられた場合、Dijkstraはグラフから始点からすべての終点までの最短経路と距離を決定します。

リンク:/uploads/initial-graph.png%20456w[]

Dijkstraアルゴリズムの核となる考えは、開始ノードとすべての可能な目的地との間のより長い経路を絶えず排除することです。

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

整定ノードとは、発信元から既知の最小距離を持つノードです。未処理ノードセットは、ソースから到達できるノードを収集しますが、開始ノードからの最小距離はわかりません。

DijkstraでSPPを解決するために従うべきステップのリストは以下のとおりです。


  • startNode

    への距離をゼロに設定します。

  • 他のすべての距離を無限大に設定します。

  • 未解決ノードセットに

    startNode

    を追加します。

  • 未処理ノードセットは空ではありませんが、

  • ** 未確定ノードセットから評価ノードを選択します。

評価ノードは、ソースからの距離が最も小さいものにします。

  • ** 最低を保つことによって直接隣人への新しい距離を計算する

各評価での距離

  • ** 未解決のノードセットにまだ解決されていないネイバーを追加します。

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


2.1. 初期化

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

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

そのため、グラフの残りの部分にある各ノードは、前任者と距離で区別されます。

リンク:/uploads/step1.png%20456w[]

初期化プロセスを終了するには、未評価ノードにノードAを追加して、評価ステップで最初に選択されるように設定する必要があります。覚えておいて、落ち着いたノードセットはまだ空です。


2.2. 評価

グラフを初期化したので、未処理集合からの距離が最も小さいノードを選択してから、解決済みノードにないすべての隣接ノードを評価します。

リンク:/uploads/step2.png%20456w[]

これは、エッジの重みを評価ノードの距離に加算してから、それを目的地の距離と比較することです。例えばノードBの場合、0 10はINFINITYよりも小さいため、ノードBの新しい距離は10、新しい前任者はAです。ノードCについても同じことが言えます。

次に、ノードAは、未処理ノードセットから解決済みノードに移動します。

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

未処理のセットに2つのノードがあるので、距離が最も小さいノード(ノードB)を選択し、グラフ内のすべてのノードを解決するまで繰り返します。

リンク:/uploads/step8.png%20456w[]

評価ステップ中に実行された反復を要約した表が、

| =================================================== =================== | |反復|未解決|解決|評価ノード| A | B | C | D | E | F | 1 | A | – | A | 0 | A-10 | A-15 | X-∞| X-∞| X-∞

| 2 | B、C | A | B | 0 | A-10 | A-15 | B-22 | X-∞| B-25

| 3 | C、F、D | A、B | C | 0 | A-10 | A-15 | B-22 | C-25 | B-25

| 4 | D、E、F | A、B、C | D | 0 | A-10 | A-15 | B-22 | D-24 | D-23

| 5 | E、F | A、B、C、D | F | 0 | A-10 | A-15 | B-22 | D-24 | D-23

| 6 | E | A、B、C、D、F | E | 0 | A-10 | A-15 | B-22 | D-24 | D-23

|

ファイナル

|



|

ALL

|

NONE

|

0

|

A-10

|

A-15

|

B-22

|

D-24

|

D-23

| =================================================== =======================

たとえば、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
}

ノードは、

shortestPath

を参照した

name



LinkedList

、ソースからの

distance

、および

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
}


adjacentNodes

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


shortestPath

属性については、開始ノードから計算された最短パスを記述するノードのリストです。

デフォルトでは、初期化ステップで説明したように、すべてのノード距離は

Integer.MAX

VALUE__で初期化され、無限距離がシミュレートされます。

それでは、Dijkstraアルゴリズムを実装しましょう。

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;
}


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;
}

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);
    }
}

必要なものがすべて整ったので、記事の主題であるサンプルグラフにDijkstraアルゴリズムを適用しましょう。

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);

計算後、グラフ内の各ノードに

shortestPath

および

distance

属性が設定されます。これらを繰り返して、結果が前のセクションの結果と正確に一致することを確認できます。


4結論

この記事では、DijkstraアルゴリズムがSPPをどのように解決し、それをJavaで実装するかを説明しました。

この単純なプロジェクトの実装は以下のhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-2[GitHubプロジェクトリンク]にあります。