ビッグデータに関するDijkstraのアルゴリズムの研究。グラフ。 Dijkstraのアルゴリズムを使用して、2つの頂点間の最短距離を見つけます。アルゴリズムの並列実装の可能な方法と機能

Dijkstraのアルゴリズムは、無向グラフの頂点間の最短パスを見つけるように設計されています。

アルゴリズムの考え方は次のとおりです：最初に、ゼロに等しい最初の頂点へのパスを選択し、この頂点をすでに選択されている頂点のセットに入力し、残りの選択されていない頂点までの距離を決定します。次の各段階で、次に選択された頂点（距離が最小）を見つけ、選択されていない頂点のセットからいくつかの頂点にエッジで接続します（この距離は、選択した頂点までの距離にエッジの長さを加えたものに等しくなります）。

例1。 上からグラフ上で最短パスを見つける L 頂点に D （図10.7）。

図： 10.7。

一連のステップの形式でアルゴリズムを記述しましょう（表10.1）。 ステップ 1.最初の頂点からの距離を決定します L 誰よりも先に。

表10.1

Dijkstraの方法（最初のステップ）

選択済み	選択した頂点へのパス	選択されていない頂点
選択済み	選択した頂点へのパス

ステップ 2.から最小距離を選択します L 前に; 見つかったピークに新しく選択されたものとして扱われます。見つかった最小距離が、新しい頂点からのエッジの長さに追加されますに誰よりも先に。から最小距離を選択しますに前 N。新しいピーク N 選択したものと見なします（表10.2）。

表10.2

Dijkstraの方法（2番目のステップ）

選択済み	選択した頂点へのパス	選択されていない頂点
選択済み	選択した頂点へのパス

わかりやすくするために、以下では、記号ooの代わりに記号「-」を付けます。

ステップ 3.上からの距離を決定します N l 残りのすべてについて（ L そして に）、 表に示すように。 10.3。

表10.3

Dijkstraの方法（第3ステップ）

選択済み	選択した頂点へのパス	選択されていない頂点
選択済み	選択した頂点へのパス

上からの距離 L 上部全体 Nから トップス G 従来の18ユニットに相当します。この距離は距離よりも大きい LB + BG \u003d 16の従来型ユニット。その結果、将来的には考慮されません。同様の構造を続けて、テーブルをコンパイルします。 10.4。したがって、頂点間の最短パスの長さが求められます。 L そして D （従来の44ユニット）。

パスの軌道は次のように決定されます。最後の頂点から最初の頂点への逆ルックアップを実行します。上に対応する列を下から上に見て、最小値の最初の出現を修正します。頂点に対応する列 D、初めて、44の従来型ユニットの最小長が4行目の下部に表示されました。この線は頂点を示します S、どちらに行くべきか、つまり次に、頂点に対応する列を検討する必要があります S。

表10.4

選択した頂点	選択した頂点へのパス	選択されていない頂点
選択した頂点	選択した頂点へのパス

この列では、27の従来の単位の最小長が次の頂点を示します G、どこに行くべきかなど。したがって、パスの軌道を取得します。 （L、B、G、S、D）。

例8。 グラフ上で1番目と7番目の頂点の間の最短パスを見つけます（図10.8）。

次に選択された頂点を決定します（表10.5）。この頂点までの距離は最小で、選択されていない頂点のセットに属する頂点の1つにエッジで接続されます（この距離は、選択された頂点までの距離にエッジの長さを加えたものに等しくなります）。

図： 10.8。グラフ （a） および対応する隣接行列 （b）

Dijkstraの方法のテーブル実装

表10.5

選択済み	選択した頂点へのパス	選択されていない頂点
選択済み	選択した頂点へのパス





6時に

最後の頂点から最初の頂点への逆ルックアップを実行します。

上に対応する列を下から上に見て、最初に出現する最小値を修正します。最短パスは次のようになります （V 7-V 5-V 2-Y（）。

そして 制御に関する質問

1.アルゴリズムの理論的な複雑さは何ですか：意思決定ツリーの構築、動的プログラミング、およびDijkstra？
2.有向グラフと無向グラフに決定ツリーを使用することの特徴は何ですか？
3.適用された問題の解決策として、グラフ内の特定の頂点間の最短距離を決定するためのアルゴリズムはありますか？
4.作業で検討されたダイクストラのアルゴリズムは、有向グラフの最短距離の決定に適用できますか？
5. Dijkstraのアルゴリズムはどのように機能しますか？
6.グラフ内の頂点間の最短距離を決定する問題に関して、動的プログラミングアルゴリズムはどのように機能しますか？

頂点とエッジを持つ有向または無向の加重グラフが表示されます。すべてのエッジの重みは負ではありません。いくつかの開始頂点が示されています。頂点から他のすべての頂点までの最短パスの長さを見つけ、最短パス自体を導出する方法を提供する必要があります。

この問題は「シングルソース最短パス問題」と呼ばれます。

アルゴリズム

これは、オランダの研究者が提案したアルゴリズムについて説明しています ダイクストラ （Dijkstra）1959年。

頂点ごとに、からへの最短パスの現在の長さを格納する配列を作成しましょう。最初、および他のすべての頂点の場合、この長さは無限大に等しくなります（コンピューターに実装されている場合、通常、十分に大きい数が無限大として選択され、明らかに可能なパス長よりも長くなります）。

さらに、各頂点について、まだマークされているかどうかを保存します。ブール配列を取得しましょう。最初は、すべての頂点にマークが付いていません。

Dijkstraのアルゴリズム自体は反復..。次の反復では、マークされていない頂点の中で最小の値を持つ頂点が選択されます。つまり、次のようになります。

（最初の反復で開始頂点が選択されることは明らかです。）

この方法で選択された頂点はマークされます。さらに、現在の反復では、頂点から、 リラクゼーション：頂点から出て行くすべてのエッジがスキャンされ、そのような頂点ごとに、アルゴリズムは値を改善しようとします。現在のエッジの長さを等しくすると、コード緩和の形で次のようになります。

この時点で、現在の反復が終了し、アルゴリズムは次の反復に進みます（最小値の頂点が再度選択され、そこから緩和が行われます）。この場合、最終的に、反復後、グラフのすべての頂点がマークされ、アルゴリズムはその作業を終了します。見つかった値は、からへの最短パスの望ましい長さであると述べられています。

グラフのすべての頂点が頂点から到達可能ではない場合、それらの値は無限のままであることに注意してください。アルゴリズムの最後の数回の反復でこれらの頂点が選択されることは明らかですが、これらの反復では有用な作業は生成されません（無限の距離では他の頂点を緩和できないため、無限の距離でも）。したがって、距離が無限の頂点が選択された頂点になるとすぐに、アルゴリズムを停止できます。

パスの復元..。もちろん、通常、最短パスの長さだけでなく、パス自体も取得する必要があります。頂点から任意の頂点への最短パスのその後の復元に十分な情報を保持する方法を示しましょう。このために、いわゆる 祖先配列：各頂点について、頂点への最短パスの最後から2番目の頂点の番号が格納されている配列。ここでは、ある頂点への最短パスを取得し、このパスから最後の頂点を削除すると、ある頂点で終わるパスが取得され、このパスがその頂点の最短パスになるという事実を使用します。したがって、この祖先の配列を所有している場合は、現在の頂点から開始頂点に到達するまで祖先を取得するたびに、それに沿って最短パスを復元できます。したがって、目的の最短パスを取得しますが、逆の順序で記述します。したがって、トップへの最短パスは次のとおりです。

この祖先の配列を構築する方法を理解することは残っています。ただし、これは非常に簡単に実行されます。リラックスが成功するたびに、つまり選択した頂点からある頂点までの距離が改善された場合、その頂点の祖先が頂点であると書き留めます。

証拠

基本的なステートメントDijkstraのアルゴリズムの正しさの基礎となる、は次のとおりです。頂点がマークされた後、その頂点までの現在の距離はすでに最短であり、したがって、それ以上変化しないと述べられています。

証拠誘導によって行われます。最初の反復では、その有効性は明らかです-私たちが持っている頂点の場合、それはそれへの最短パスの長さです。ここで、このステートメントを以前のすべての反復に当てはめます。すでにマークされているすべての頂点。現在の反復の実行後に違反していないことを証明しましょう。現在の反復で選択された頂点、つまりアルゴリズムがマークしようとしている頂点。それが実際にそれへの最短パスの長さに等しいことを証明しましょう（この長さをで示します）。

頂上への最短経路を検討してください。明らかに、このパスは2つのパスに分割できます。1つはマークされた頂点のみで構成され（少なくとも開始頂点はこのパスにあります）、残りのパス（マークされた頂点を含めることもできますが、常にマークされていないもので始まります）。パスの最初の頂点と、パスの最後の頂点で示します。

まず、頂点のステートメントを証明しましょう。私たちは平等を証明します。ただし、これはほぼ明らかです。結局のところ、前の反復の1つで、頂点を選択し、そこから緩和を実行しました。（頂点の選択のおかげで）への最短パスはへの最短パスにエッジを加えたものに等しいので、から緩和を実行すると、値は実際に必要な値に設定されます。

エッジのコストは非負であるため、最短パスの長さ（そしてそれは今証明されたものと同じです）は、頂点までの最短パスの長さを超えません。（結局のところ、Dijkstraのアルゴリズムは可能なよりも短いパスを見つけることができなかった）ことを考えると、最終的に次の比率が得られます。

一方、u、uはマークされていない頂点であるため、現在の反復では、選択されたのは頂点であり、頂点ではないため、別の不等式が得られます。

これらの2つの不平等から、等式を結論付け、次に、取得する前に見つかった関係から、次のようにします。

q.E.D.

実装

したがって、Dijkstraのアルゴリズムは反復によって表され、それぞれで最小値のマークされていない頂点が選択され、この頂点がマークされ、次にこの頂点から出て行くすべてのエッジがスキャンされ、各エッジに沿ってエッジのもう一方の端の値を改善しようとします。

アルゴリズムの実行時間は次のとおりです。

これらの操作の最も単純な実装では、操作は頂点の検索に費やされ、操作は1つの緩和に費やされ、最後の漸近アルゴリズムは次のとおりです。

実装:

const int INF \u003d 1000000000; int main（）（int n; ... read n ... vector< vector < pair< int ,int > \u003e\u003e g（n）; ...グラフを読む... int s \u003d ...; //開始頂点ベクター< int > d（n、INF）、p（n）; d [s] \u003d 0; ベクター< char > u（n）; for（int i \u003d 0; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

ここでは、グラフは隣接リストの形式で保存されます。各頂点について、リストにはこの頂点から発するエッジのリストが含まれています。ペアのリスト\u003e。ここで、ペアの最初の要素はエッジがつながる頂点であり、2番目の要素はエッジの重みです。

アルゴリズムDemykstra（Dijkstraのアルゴリズム）-1959年にオランダの科学者E. Dijkstraによって発明されたグラフ上のアルゴリズム。グラフの頂点の1つから他のすべての頂点までの最短距離を見つけます。このアルゴリズムは、負の重みのエッジがないグラフに対してのみ機能します。このアルゴリズムは、プログラミングで広く使用されています。たとえば、OSPFプロトコルでは、Shortest PathFirstとも呼ばれるループパスを排除するために使用されます。

Dijkstraのアルゴリズムは、すべてのエッジの重みが非負（（u、v）？0 for all（u、v）E）である、初期頂点sを持つ重み付き有向グラフG \u003d（V、E）の1つの頂点からの最短パスの問題を解決します。グラフのエッジが等しくない場合は、このアルゴリズムを使用することをお勧めします。

問題の定式化。グラフがあります。その頂点のいくつかは頂点1として指定されています。頂点1から各グラフ頂点への最小パスを見つける必要があります。最小パスは、パスに沿った価格の合計が最小のパスです。価格は、エッジの重みである負でない数値です。

アルゴリズムのアイデア。このアイデアは、次の明白なステートメントに基づいています。頂点からの最小パスを構築しましょう。 a 頂点Bに接続します。そして、頂点Bをいくつかの頂点iに接続します。 Ciが頂点Bから頂点iへのパスのコストを表すとします。 Ciから最小値を選択しましょう。次に、ポイントBからのパスの最小継続は、選択された値を通過します。

このステートメントは実際には証明を必要としません。そして、それから非常に深刻な結果が生じます。最小パスがすでに通過する頂点のセットがあるとします。そのようなセットが存在することが保証されます。これが頂点1です。上記で定式化されたアサーションにより、既存の頂点のセットにもう1つの頂点を追加でき（以下、それらを選択済みと呼びます）、グラフ内の頂点の数が有限であるため、有限のステップ数でグラフのすべての頂点が選択されます。、そしてこれが解決策になります。

Dijkstraのアルゴリズムの本質は、選択した頂点のセットにもう1つの頂点を追加する手順にあります。この手順は、次の2つのステップで構成されます。

1.選択した頂点に付随する頂点のセットを作成し、その中から最低価格の頂点を見つけます。見つかった頂点が、選択した頂点のセットに追加されます。

2.選択した頂点に付随する一連の頂点を作成し、それらの新しい価格を決定します。新しい頂点価格は、選択した頂点のセットから指定された頂点までのパスの最小価格です。新しい価格は次のように構成されます。

a。選択された頂点のセット内の選択されていない頂点について、指定された頂点に付随する頂点のサブセットが決定されます。

b。選択したサブセットの各頂点について、指定されたサブセットへのパスのコストが決定されます。

c。最低価格が決定されます。この価格がトップの価格になります。

このアルゴリズムは、エッジ価格とトップ価格の2種類の価格で機能します。リブの価格は一定です。ピークの価格は常に再計算されます。これらの価格の意味は異なります。エッジのコストは、頂点からこのエッジで接続された頂点に移動するコストです。そして、トップの価格は最小パスの価格です。もう1つの重要な注意点は、暫定価格の再計算に関するものです。実際、他のピークの暫定価格を変更する理由がないため、最後のステップで選択したセットに追加されたトップに接続されているピークのみの暫定価格を再計算することは理にかなっています。

すべての価格（たとえば、小道や旅行の裏地）はマイナスではないことが知られています。すべてのi \u003d 1に対して最小のパスコスト1-\u003e iを見つけます。時間O（n2）のn。

アルゴリズムの操作中に、いくつかの都市が選択されます（最初は都市1のみ、最後はすべて）。ここで：

選択した都市iごとに、パス1-\u003e iの最小コストが保存されます。選択した都市のみを通過するパスで最小値に達することが知られています。

割り当てられていない都市iごとに、パス1-\u003e iの最小コストが格納され、選択された都市のみが中間都市として使用されます。

選択された都市のセットは、次の注釈に基づいて拡張されます。選択されていないすべての都市の中で、格納されている数が最小の都市を採用する場合、この数が真の最低コストです。確かに、もっと短い方法があります。このパスで最初に選択されていない都市を考えてみましょう-そのパスはもっと長いです！（ここでは、価格の非負性が不可欠です。）

選択した都市を選択した都市に追加したら、選択していない都市用に保存されている情報を調整する必要があります。この場合、新しい都市が最後の移動ポイントとなるパスのみを考慮するだけで十分であり、新しい都市への移動の最小コストがすでにわかっているため、これは簡単に実行できます。

言い換えると、Vからの各頂点には、ラベルが割り当てられます。これは、この頂点からaまでの既知の最小距離です。アルゴリズムは段階的に機能します。各段階で、1つの頂点に「アクセス」し、ラベルを減らしようとします。すべての頂点にアクセスすると、アルゴリズムは終了します。

初期化。一番上のマーク a 等しいと見なされます 0 、残りの頂点のラベルは無限大です。これはからの距離が a 他のピークへはまだ不明です。グラフのすべての頂点は、未訪問としてマークされます。

アルゴリズムステップ。すべての頂点にアクセスすると、アルゴリズムは終了します。それ以外の場合は、まだ訪問されていない頂点から、頂点 u最小限のラベルで。あらゆる種類のルートを検討します u 最後から2番目のアイテムです。頂点に接続された頂点 u エッジは、この頂点のネイバーと呼ばれます。ネイバーごとに、現在のラベルの合計に等しい新しいパス長を検討します u と接続するエッジの長さ u この隣人と。結果の長さがネイバーのラベルよりも短い場合は、ラベルをこの長さに置き換えます。すべての隣人を考慮した後、頂点をマークします u 訪問したとおりに、手順を繰り返します。

Dijkstraのアルゴリズムは常に、処理のために最短パス推定値が最も低い頂点を選択するため、貪欲なアルゴリズムに属していると言えます。

Dijkstraのアルゴリズムのスキームをより詳細に説明しましょう。

アルゴリズムは、それぞれN（\u003dネットワーク頂点の数）番号の3つの配列を使用します。最初の配列Aには、0（上部はまだ考慮されていません）と1（上部はすでに考慮されています）の2つの値を持つラベルが含まれています。 2番目の配列Bには、距離（対応する頂点までの現在の最短距離）が含まれています。 3番目の配列cには、頂点の数が含まれています。k番目の要素C [k]は、ViからVkへの現在の最短パス上の最後から2番目の頂点の数です。距離行列Dは、円弧Dの長さを定義します。そのようなアークがない場合、Dには「マシンの無限大」に等しい大きな数のBが割り当てられます。

今、私たちは説明することができます：

1.（初期化）。 1からNまでのループで、配列Aをゼロで埋めます。配列Cをiで埋めます。行列Dのi番目の行を配列Bに転送します。A[i]：\u003d 1; C [i]：\u003d 0（iは開始頂点の番号です）

2.（一般的な手順）。マークされていないもの（つまり、A [k] \u003d 0であるk）の中から最小値を見つけます。インデックスjで最小値を達成します。 B [j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] + D、次に（B [k]：\u003d B [j] + D; C [k]：\u003d j）（条件は、パスVi。VkがパスVi。VjVkよりも長いことを意味します）。（すべてのA [k]がマークされている場合、ViからVkまでのパスの長さはB [k]に等しくなります。ここで必要です）最短パスに含まれる頂点を列挙します）。

3.（回答の発行）。（ViからVkへのパスは、次の手順で逆の順序で返されます:)

2.zを発行します。

3. z：\u003d C [z]。 z \u003dОの場合は終了、それ以外の場合は3.2に進みます。

アルゴリズムを実行するには、N個の要素の配列BをN回スキャンする必要があります。 Dijkstraのアルゴリズムには、2次の複雑さがあります：O（n2）。

以下は、Dijkstraのアルゴリズムのブロック図です（図2を参照）。

図2。 Dijkstraのアルゴリズムフローチャート

アルゴリズムの開始時に、最初の頂点の距離はゼロに設定され、他のすべての距離は大きな正の数（グラフで可能な最大パスよりも大きい）で埋められます。 flags配列はゼロで埋められます。次に、メインループが開始されます。

サイクルの各ステップで、最小距離とゼロに等しいフラグを持つ頂点を探しています。次に、フラグを1に設定し、それに隣接するすべての頂点をチェックします。その中の距離が現在の頂点までの距離とエッジの長さの合計よりも大きい場合は、それを減らします。すべての頂点のフラグが1に等しくなると、サイクルは終了します。

Dijkstraのアルゴリズムを使用して最短パスを見つける問題を解決します。
X0からX7への最短パスを見つけます。グラフは、コストマトリックスの要素によって与えられます

このグラフを作成しましょう

要素X0から始めて、それにラベル0を割り当て、そのすべての隣接要素を考慮してみましょう。まだマークがないので、適切な長さを割り当てます。

すべてのネイバーX0が考慮されたので、それをマークして頂点X1に移動します。 ITSはX0、X2、X4に隣接していますが、X0はマークされているため、考慮しません。 X2の場合：、ラベルを残します。

X4の場合：、ラベルを交換してください。頂点X1のすべての隣接が考慮されているので、マークを付けます

トップX2に移動します。 ITSネイバーX0、X1、X3、X4、X5、X6ですが、X0、X1はマークされているため、考慮しません。
X3の場合：、ラベルを残します。
X5の場合：、ラベルを交換してください。
X4の場合：、ラベルを残します。
X6の場合：、ラベルを交換してください。
頂点X2のすべての隣接が考慮されているので、マークを付けます。

トップX3に移動します。 ITSネイバーX0、X2、X6ですが、X0、X2はマークされているため、考慮しません。
X6の場合：、ラベルを残します。
頂点X3のすべての隣接が考慮されているので、マークを付けます。

トップX4に移動します。 ITSネイバーX1、X2、X5、X7ですが、X1、X2はマークされているため、考慮しません。
X5の場合：、ラベルを交換してください。
X7の場合：、ラベルを交換してください。
頂点X4のすべての隣接が考慮されているので、マークを付けます。

トップX5に移動します。 ITSネイバーX2、X4、X6、X7ですが、X2、X4はマークされているため、考慮しません。
X6の場合：、ラベルを残します。
X7の場合：、ラベルを残します。
頂点X5のすべての隣接が考慮されているので、マークを付けます。

トップX6に移動します。 ITSネイバーX2、X3、X5、X7ですが、X2、X3、X5はマークされているため、考慮しません。
X7の場合：、ラベルを残します。
頂点X6のすべての隣接が考慮されているので、マークを付けます。そして、残りのX7にマークを付け、すべての頂点が考慮されます。

結論：X0からX7への最短パスの長さは101で、このパスはX7-X4-X1-X0です。

5.4.3。最短経路の問題とその解決のためのDijkstraのアルゴリズム

ダイグラフを与えましょう G(V, E）、各アークには番号が割り当てられています
と呼ばれる 弧の長さ.

定義。 長さパスは、このパスを構成する円弧の長さの合計と呼ばれます。 最短パスの問題このように置かれます。

オプション1。 最短パス（最小長のパス）の長さと固定頂点からのパス自体を見つけます s グラフの他のすべての頂点に。

オプション2。 与えられたグラフの頂点のすべてのペア間の最短パスとパス自体の長さを見つけます。

グラフに負の長さの円弧が含まれている場合、問題に解決策がない可能性があります（意味が失われます）。これは、グラフに負の長さの輪郭が含まれている可能性があるためです。負の長さの輪郭の存在は、パスの長さを等しくすることができることを意味します
..。また、負の長さの輪郭がない場合、最短のパスが存在し、最短のパスは単純なチェーンになります。

最短パスが存在する場合、そのサブパスのいずれかが対応する頂点間の最短パスでもあることに注意してください。

最短経路の問題を解決するためのDijkstraのアルゴリズム。

アルゴリズムは正の長さの円弧で機能し、固定頂点からの最短パスを決定します s グラフの他のすべての頂点に。これらの頂点を示しましょう v 1 , v 2 ,…, v n .

定義。 トップと呼ぼう u 上に寄り添う sトップより vからの最短パスの長さ s 前 u からの最短パスの長さよりも短い s 前 v..。トップスと言います u そして v 等距離 上から sからの最短パスの長さが s 前 u とから s 前 v 一致。

Dijkstraのアルゴリズムは、頂点に近接しているという意味で、グラフの頂点を順番に並べます。 s そして、以下の基本原則に基づいています。

円弧の長さが正の数の場合、

に最も近い s トップはそれ自体です。からの最短パス長 s 前 s 0に等しい;

に最も近い s 以外の頂点 s、から嘘 s 1つの弧の距離で-頂点を離れるすべての弧の中で最も短い s;

からの最短パスの中間頂点 s いくつかの頂上へ v 近くにあります s最終頂点より v;

次の順序付けられた頂点への最短パスは、すでに順序付けられた頂点のみを通過できます。

アルゴリズムがすでに頂点を順序付けていると仮定します v 1 , v 2 … v k . で示しましょう
,
一番上までの最短パスの長さ v 私 .

セットの頂点の1つから始まる元のグラフのすべての円弧を検討してください
そして、まだ順序付けられていない頂点で終わります。たとえば、そのようなアークごとに
、合計を計算します
..。この合計は、からのパスの長さに等しくなります s に yここで頂点 v 私最後から2番目の頂点であり、 s に v 私 -接続するすべてのパスの最短 s そして v 私 .

これにより、からのすべてのパスの長さが決まります s まだ順序付けられていない頂点に、中間の頂点は数からの頂点のみです k に最も近い s..。これらのパスの最短を一番上で終了させます w..。次に w そこには
に近い s バーテックス。

技術的には、Dijkstraのアルゴリズムに従ったアクションは、頂点ラベル装置を使用して実行されます。頂点ラベル v として示される
..。ラベルは、からのパスの長さに等しい数です。 s 前 v..。タグは一時的なものと永続的なものに分けられます。各ステップで、1つのマークのみが一定になります。これは、その値が対応する頂点への最短パスの長さに等しく、この頂点自体が順序付けられていることを意味します。次に順序付けられた頂点の番号は文字で示されます r.

アルゴリズムの説明.

ステップ1。 （初期設定）..。置く
このラベル定数を考慮してください。置く
,
これらのマークを一時的なものとして扱います。置く
.

ステップ2。 （一般的な手順）。 繰り返す n グラフのすべての頂点が順序付けられるまでの時間。

タイムスタンプを再計算する
順序付けられていない頂点 v 私、頂点から出て行く弧を含む r、規則により

タイムスタンプが最小の頂点を選択します。そのような頂点が複数ある場合は、いずれかを選択してください。

しましょう w- タイムスタンプが最小の頂点。ラベルを読む
一定して置く
.

Dijkstraのアルゴリズムのステップは、各列がグラフの頂点に対応するテーブルに便利に表示されます。表の行は、一般的な手順の繰り返しに対応しています。

例. 図のグラフの場合。 4.頂点から最短パスを見つける
グラフの他のすべての頂点に。エッジとは、同じ長さの2つの反対方向の円弧を意味します。

決定。 テーブル 1には、各ステップでの頂点のラベルが含まれています。恒久的なラベルには「+」記号が付いています。頂点ラベルの計算方法を詳しく説明しましょう。

頂点1から、円弧は頂点2、5、6に出ます。これらの頂点のラベルを再計算し、テーブルの2番目の行に入力します。

頂点マーク6が一定になり、
.

アークは頂点6からまだ順序付けられていない頂点2、5、8、9に出現します。タイムスタンプを再計算します

表の3行目に記入します。タイムスタンプの最小値は3（頂点ラベル9）、
.

頂点9から、弧はまだ順序付けられていない頂点5、8、11、12に出ます。

表の4行目に記入します。この行では、2つの頂点2と12の最小タイムスタンプが4になっています。最初に、たとえば頂点2を並べ替えます。次に、次のステップで頂点12を並べ替えます。

表1

そう、

アークは頂点2からまだ順序付けられていない頂点3、4、5に移動します。これらの頂点のタイムスタンプを再計算します。

表の5行目に記入します。タイムスタンプの最小値は4（頂点ラベル12）、
.

表の6行目に記入します。タイムスタンプの最小値は5（頂点ラベル5）、
.

表の7行目に記入します。頂点8の定数ラベルになります（5に等しい）、
.

Vertex11が注文されました。

アークは頂点11から順序付けられていない頂点7、10に移動します。これらの頂点のタイムスタンプを再計算します。

Vertex4は永続的なラベルを取得します。

頂点4から、円弧は順序付けられていない頂点3、7に移動します。タイムスタンプを再計算します。

頂点3の順序付け。

表の12行目に記入します。このステップでは、最後の順序付けされていない頂点10を順序付けます。

最短パスツリーを構築します。

最短パスツリーは、上部をルートとする有向ツリーです。 S ..。このツリーのすべてのパスは、このグラフの最短パスです。

最短パスツリーはテーブルから作成され、頂点ごとに永続的なラベルを受け取った順序でテーブルに含まれます。最初のルートはツリーに含まれています-頂点 S .

この例では、最短パスツリーを作成しましょう。

まず、ツリーにルート（頂点1）を含めます。次に、円弧（1,6）をツリーに含めます。次の頂点9が順序付けられ、最短パスの長さは3です。3行目に最初に番号3が表示されたとき、
..。したがって、頂点6は、頂点9への最短パスの最後から2番目の頂点です。ツリーに長さ1の円弧（6,9）を含めます。

次に、頂点2が4に等しい最短パス長で順序付けられました。この番号は最初に3行目に表示され、次のときに入力されました。
..。したがって、2番目の頂点への最短パスは円弧（6.2）に沿っています。ツリーに長さ2の円弧（6,2）を含めます。

次に、頂点12が順序付けられました。
..。番号4が4行目に初めて表示されたとき、
..。このツリーには、長さ1の円弧（9.12）が含まれています。完全な最短パスツリーを図1に示します。 5.5。

グラフに負の長さの円弧が含まれている場合、Dijkstraのアルゴリズムが間違っている可能性があります。だから、上から最短の道を探す s \u003d図のグラフの場合は1。 6、アルゴリズムは最初に頂点3、次に頂点2を順序付け、終了します。さらに、ダイクストラのアルゴリズムの観点から、頂点3へのこの最短パスは、長さ3の円弧（1,3）です。

実際、頂点3への最短パスは円弧（1,2）と（2,3）で構成され、このパスの長さは5 +（-3）\u003d 2です。

負の長さ–3の円弧（2,3）が存在するため、次の基本原則に違反しました。

に最も近い s 頂点は、1つではなく、2つの円弧の距離にあります。

最短パス1-2-3の中間頂点（頂点2）は、パス3の最終頂点よりも頂点1から（距離5で）遠くにあります。

その結果、負の長さのアークが存在すると、最短パス問題の解決が複雑になり、Dijkstraのアルゴリズムよりも複雑なアルゴリズムを使用する必要があります。