定義と問題を述べます。
グラフは複数のポイント（頂点）と呼ばれ、そのペアのいくつかはセグメント（エッジ）で接続されます。 これらのセグメントに沿って各頂点から他の頂点に到達できる場合は、グラフが接続されます。 サイクルとは、同じ頂点で開始および終了するグラフのエッジに沿ったパスです。 また、別のグラフは、各エッジが特定の数（重み）に対応する場合、重み付きと呼ばれます。 同じ頂点を接続する2つのエッジは存在できません。
各アルゴリズムは、重み付き接続の最短パスの問題を解決します。 ある頂点から別の頂点への最短経路は、通過したエッジの重みの合計が最小になるようなエッジに沿った経路です。
明確にするために、私は実生活でのそのようなタスクの例を挙げます。 国にこれらの都市を接続するいくつかの都市と道路があるとします。 さらに、各道路には長さがあります。 できる限り旅行せずに、ある都市から別の都市に行きたい。
グラフにはn個の頂点とm個のエッジがあると仮定します。
単純なものから複雑なものに移りましょう。
Floyd-Worschellアルゴリズム
次数n ^ 3の操作の数について、各頂点から各頂点までの距離を求めます。 重みは負になる場合がありますが、エッジの重みの負の合計を持つサイクルを持つことはできません（そうでない場合は、好きなだけその上を歩くことができ、毎回量を減らすことができます）。
i番目の反復で配列d [0 ... n-1] [0 ... n-1]に、パスの「転送ポイント」として厳密にiより小さい数の頂点を使用するという制限付きで、元の問題に対する答えを保存します。 -1（最初から頂点に番号を付けます）。 i番目の反復を行って、配列をi + 1番目に更新します。 これを行うには、頂点のペアごとに、i-1番目の頂点をインターチェンジとして取得しようとします。これにより回答が改善された場合は、そのままにします。 合計で、n + 1回の反復を行います。その完了後、anyを「交換」として使用でき、配列dが答えになります。
n回の繰り返しに対するn回の繰り返し、n次の合計n ^ 3回の操作。
擬似コード：
g // g[0 ... n - 1][0 ... n - 1] - , , g[i][j] = 2000000000, i j d = g for i = 1 ... n + 1 for j = 0 ... n - 1 for k = 0 ... n - 1 if d[j][k] > d[j][i - 1] + d[i - 1][k] d[j][k] = d[j][i - 1] + d[i - 1][k] d
フォードベルマンアルゴリズム
順序n * mの操作の数について、1つの頂点（番号0を指定）から他のすべての頂点までの距離を見つけます。 前のアルゴリズムと同様に、重みは負になる可能性がありますが、エッジの重みの負の合計を持つサイクルを持つことはできません。
配列d [0 ... n-1]を開始します。この配列では、i番目の反復で、厳密にi未満のエッジがパスに入るという制限付きで、元の問題に対する答えを保存します。 ピークjへのパスが存在しない場合、d [j] = 2,000,000,000（到達不可能な定数「無限大」でなければなりません）。 iの繰り返しで配列を更新するには、各エッジに沿って移動し、接続する頂点までの距離を改善する必要があります。 すべてのサイクルは非負であり、パスからサイクルを削除でき、パスの長さは悪化しないため、最短パスにはサイクルが含まれていません（これは、グラフで負のサイクルを見つける方法であることに注意してください：あるピークまでの距離が改善されたかどうか）。 したがって、最短パスの長さはn-1以下です。これは、n回目の反復の後、dが問題の答えになることを意味します。
n回の繰り返しをm回繰り返し、合計でn * m回の操作の順序。
擬似コード：
e // e[0 ... m - 1] - , (first, second - , , value - ) for i = 0 ... n - 1 d[i] = 2000000000 d[0] = 0 for i = 1 ... n for j = 0 ... m - 1 if d[e[j].second] > d[e[j].first] + e[j].value d[e[j].second] = d[e[j].first] + e[j].value if d[e[j].first] > d[e[j].second] + e[j].value d[e[j].first] = d[e[j].second] + e[j].value d
ダイクストラのアルゴリズム
順序n ^ 2の操作数について、1つの頂点（番号0を指定）から他のすべての頂点までの距離を検索します。 すべての重みは負ではありません。
各反復で、いくつかの頂点がマークされ、いくつかはマークされません。 2つの配列を開始します。mark [0 ... n-1]-頂点がマークされている場合はtrue、そうでない場合はfalse d [0 ... n-1]-マークされた頂点のみに沿って通過する最短パスの長さが「転送ポイント」として保存されます。 また、ラベル付き頂点の場合、dで示される長さが答えであるという不変式もサポートされています。 まず、頂点0のみがマークされ、0とiが重みxのエッジで接続されている場合、g [i]はxと等しく、エッジで接続されていない場合は2,000,000,000に等しく、i = 0の場合は0です。
各反復で、ラベル付けされていないものの中でdの最小値を持つ頂点を見つけ、それを頂点vとする。 次に、d [v]の値がvの答えです。 証明します。 0からvへの最短経路が「転送ポイント」としてマークされた頂点に沿って進むだけでなく、同時にd [v]よりも短いと仮定します。 このパスでマークされていない最初のピークを取得し、uと呼びます。 パスの移動部分の長さ（0〜u）はd [u]です。 len> = d [u]。ここで、lenは0からvまでの最短経路の長さです（負のエッジがないため）。ただし、lenがd [v]より小さいと仮定します。 したがって、d [v]> len> = d [u]。 しかし、vはその説明に適合しません-ラベルのないものの中で最小値d [v]を持ちません。 論争。
ここで、頂点vを太字でマークし、dを再計算します。 すべての頂点がマークされ、dが問題の答えになるまでこれを行います。
（頂点vを検索するための）n回の反復でのn回の反復、合計n ^ 2演算の順序。
擬似コード：
g // g[0 ... n - 1][0 ... n - 1] - , , g[i][j] = 2000000000, i j d = g d[0] = 0 mark[0] = True for i = 1 ... n - 1 mark[i] = False for i = 1 ... n - 1 v = -1 for i = 0 ... n - 1 if (not mark[i]) and ((v == -1) or (d[v] > d[i])) v = i mark[v] = True for i = 0 ... n - 1 if d[i] > d[v] + g[v][i] d[i] = d[v] + g[v][i] d
疎グラフ用のダイクストラのアルゴリズム
これは、ダイクストラアルゴリズムと同じですが、 m * log（n）のオーダーの操作数に対して実行されます 。 mはn ^ 2のオーダーであることに注意する必要があります。つまり、ダイクストラのアルゴリズムのこのバリエーションは、古典的なアルゴリズムよりも常に高速ではなく、小さいmに対してのみです。
ダイクストラのアルゴリズムには何が必要ですか？ dの値で最小の頂点を見つけ、ある頂点でdの値を更新できる必要があります。 古典的な実装では、単純な配列を使用し、n個の操作の順序でdの最小頂点を見つけ、1回の操作で更新できます。 バイナリヒープを使用します （多くのオブジェクト指向言語では組み込みです）。 ヒープは操作をサポートします：要素をヒープに追加（ログ（n）操作の順序）、最小要素を検索（1操作）、最小要素を削除（ログ（n）操作の順序）、nはヒープ内の要素の数です
配列d [0 ... n-1]（その値は前と同じです）とqの束を作成します。 ヒープには、頂点番号vとd [v]からペアを格納します（ペアはd [v]で比較する必要があります）。 ヒープ内にダミー要素がある場合もあります。 これは、d [v]の値が更新されたために発生しますが、ヒープで変更することはできません。 したがって、ヒープには同じ頂点番号を持つが、d値が異なる複数の要素が存在する可能性があります（ただし、ヒープには頂点がm個しかありませんが、これは保証されます）。 ヒープの最小値を取得するとき、この要素がダミーかどうかを確認する必要があります。 これを行うには、ヒープ内のdの値とその実際の値を比較するだけで十分です。 そして、バイナリ配列の代わりにグラフを書くために、リストの配列を使用します。
ヒープに要素を追加するm回、m * log（n）回の操作の順序を取得します。
擬似コード：
g // g[0 ... n - 1] - , i- : first - , i- , second - d[0] = 0 for i = 0 ... n - 1 d[i] = 2000000000 for i in g[0] // python style d[i.first] = i.second q.add(pair(i.second, i.first)) for i = 1 ... n - 1 v = -1 while (v = -1) or (d[v] != val) v = q.top.second val = q.top.first q.removeTop mark[v] = true for i in g[v] if d[i.first] > d[v] + i.second d[i.first] = d[v] + i.second q.add(pair(d[i.first], i.first)) d