algorithm
ダイクストラのアルゴリズム

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

続行する前に、Adjacency MatrixとBFSについて簡単に考えておくことをお勧めします

ダイクストラのアルゴリズムは、単一ソース最短経路アルゴリズムとして知られている。これは、道路ネットワークなどのグラフ内のノード間の最短経路を見つけるために使用されます。 1956年にEdsger W. Dijkstraによって考案され、3年後に出版された。

Breadth First Search（BFS）検索アルゴリズムを使用して最短経路を見つけることができます。このアルゴリズムはうまくいきますが、問題は、各パスを通過するコストが同じであることを前提としています。つまり、各エッジのコストは同じです。 Dijkstraのアルゴリズムは、各経路のコストが同じでない最短経路を見つけるのに役立ちます。

まず、Dijkstraのアルゴリズムを書くためにBFSを修正する方法を見てみましょう。次に、それを完全なDijkstraのアルゴリズムにする優先順位キューを追加します。

ソースからの各ノードの距離がd []配列に保持されているとしましょう。同様に、 d [3]は、 d [3]時間がソースからノード3に到達するのにかかる時間を表す。距離がわからない場合は、 無限をd [3]に格納します 。また、 コスト[u] [v]をuvのコストとする。つまり、 uノードからvノードに行くにはコスト[u] [v]がかかります。

エッジリラクゼーションを理解する必要があります。たとえば、あなたの家からは、それがソースであるとしましょう。Aに行くには10分かかります。そして、場所Bに行くのに25分かかります。我々は持っています、

d[A] = 10
d[B] = 25

今度はA地点からB地点に行くのに7分かかるとしましょう。

cost[A][B] = 7

その後、我々は10 + 7 = 17分、代わりに25分かかりますBを配置しようと、場所Aから、 ソースからAを配置するために行くことによって、ソースからBを配置するために行くことができます。そう、

d[A] + cost[A][B] < d[B]

次に、

d[B] = d[A] + cost[A][B]

これはリラクゼーションと呼ばれます。我々は、Vのノード間のuから行きますとD場合は、[U] +コスト[u]が[V] <D [V]、我々は、Dを更新します[V] = D [U] +コスト[U] [V]。

BFSでは、ノードを2回訪問する必要はありませんでした。ノードが訪問されたかどうかだけを確認しました。訪問されなかった場合は、ノードをキューにプッシュして訪問先としてマークし、距離を1ずつ増やします.Dijkstraでは、ノードをキューにプッシュして訪問先で更新する代わりに、新しいエッジを緩和または更新します。一例を見てみましょう：

ノード1がソースであるとしましょう。次に、

d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)

まだ距離がわからないので、 d [2]、d [3] 、 d [4]を無限に設定する 。 ソースの距離はもちろん0です。さて、 ソースから他のノードに移動し、それらを更新できる場合は、それらをキューにプッシュします。例えば、我々は1-2を横切るでしょう。 d [1] + 2 <d [2]として 、 d [2] = 2とする 。同様に、我々はd [3] = 5とするエッジ1-3を横切る。

5はノード3に行くために交差できる最短距離ではないことが明確に分かります。したがって、BFSのようにノードを1回だけトラバースすることはここでは機能しません。 エッジ2-3を使用してノード2からノード3に行く場合、 d [3] = d [2] + 1 = 3を更新することができる。そのため、1つのノードを何度も更新することができます。あなたは何回尋ねますか？ノードを更新できる最大回数は、ノードのin-degreeの数です。

任意のノードを複数回訪問するための擬似コードを見てみましょう。単にBFSを変更します。

procedure BFSmodified(G, source):
Q = queue()
distance[] = infinity
Q.enqueue(source)
distance[source]=0
while Q is not empty
    u <- Q.pop()
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
        end if
    end for
end while
Return distance

これは、ソースからすべてのノードの最短パスを見つけるために使用できます。このコードの複雑さはあまり良くありません。理由は次のとおりです。

BFSでは、 ノード1から他のすべてのノードに移動するとき、 先着順の方法に従います。たとえば、 ノード2を処理する前にソースからノード3に行きました。 ソースからノード3に行くと、 ノード4は5 + 3 = 8として更新されます 。再びノード3をノード2から更新する場合、ノード4を3 + 3 = 6として再度更新する必要があります 。したがって、 ノード4は2回更新される。

Dijkstraは、 First come、first serveメソッドの代わりに、最も近いノードを最初に更新すれば、更新が少なくて済みます。前にノード2を処理した場合、 ノード3は前に更新されていて、それに応じてノード4を更新した後、簡単に最短距離を取得します。アイデアは、 ソースに最も近いキューであるノードから選択することです 。ここでPriority Queueを使用すると、キューをポップすると、 ソースから最も近いノードuが取得されます 。どのようにそれを行うのだろうか？これでd [u]の値をチェックします。

擬似コードを見てみましょう：

procedure dijkstra(G, source):
Q = priority_queue()
distance[] = infinity
Q.enqueue(source)
distance[source] = 0
while Q is not empty
    u <- nodes in Q with minimum distance[]
    remove u from the Q
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
            Q.enqueue(v)
        end if
    end for
end while
Return distance

擬似コードは、 ソースから他のすべてのノードまでの距離を返します。 1つのノードvの距離を知りたい場合は、 vがキューからポップされたときに値を返すことができます。

負のエッジがある場合、Dijkstraのアルゴリズムは機能しますか？負のサイクルがある場合は、無限ループが発生します。これは毎回コストを削減し続けるためです。負のエッジがあっても、ダイクストラは目標がポップされた直後に復帰しなければ動作しません。しかし、それはDijkstraアルゴリズムではありません。我々は、負のエッジ/サイクルを処理するためにBellman-Fordアルゴリズムを必要とする。

複雑：

BFSの複雑さは、 O（log（V + E））であり、 Vはノードの数であり、 Eはエッジの数である。 Dijkstraの場合、複雑さは似ていますが、 Priority QueueのソートにはO（logV）が必要です。したがって、全体の複雑さは、 O（Vlog（V）+ E）

以下は、Adjacency Matrixを使ったDijkstraの最短経路アルゴリズムを解くJavaの例です

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{
    static final int V=9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

    void dijkstra(int graph[][], int src)
    {

        Boolean sptSet[] = new Boolean[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        printSolution(dist, V);
    }

    public static void main (String[] args)
    {
    int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                {0, 0, 2, 0, 0, 0, 6, 7, 0}
                                };
        ShortestPath t = new ShortestPath();
        t.dijkstra(graph, 0);
    }
}

プログラムの期待される出力は

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14