Design-and-analysis-of-algorithms-shortest-paths
DAA-最短経路
ダイクストラのアルゴリズム
ダイクストラのアルゴリズムは、有向グラフ_G =（V、E）の単一ソース最短パス問題を解決します。ここで、すべてのエッジは非負です（つまり、各エッジ_（u、v）≥0 u、v）ЄE）。
次のアルゴリズムでは、最小のキーを持つノードを抽出する1つの関数 Extract-Min（） を使用します。
Algorithm: Dijkstra’s-Algorithm (G, w, s)
for each vertex v Є G.V
v.d := ∞
v.∏ := NIL
s.d := 0
S := Ф
Q := G.V
while Q ≠ Ф
u := Extract-Min (Q)
S := S U {u}
for each vertex v Є G.adj[u]
if v.d > u.d + w(u, v)
v.d := u.d + w(u, v)
v.∏ := u分析
このアルゴリズムの複雑さは、Extract-Min関数の実装に完全に依存しています。 最小検索関数が線形検索を使用して実装されている場合、このアルゴリズムの複雑さは O（V ^ 2 ^ + E） です。
このアルゴリズムでは、 _ Extract-Min（）' 関数が最小のキーで _Q' からノードを返すmin-heapを使用すると、このアルゴリズムの複雑さをさらに減らすことができます。
例
頂点 1 と 9 をそれぞれ開始頂点と宛先頂点として考えてみましょう。 最初は、開始頂点を除くすべての頂点に∞のマークが付けられ、開始頂点に 0 のマークが付けられます。
| Vertex | Initial | Step1 V1 | Step2 V3 | Step3 V2 | Step4 V4 | Step5 V5 | Step6 V7 | Step7 V8 | Step8 V6 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | ∞ | 5 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | ∞ | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 4 | ∞ | ∞ | ∞ | 7 | 7 | 7 | 7 | 7 | 7 |
| 5 | ∞ | ∞ | ∞ | 11 | 9 | 9 | 9 | 9 | 9 |
| 6 | ∞ | ∞ | ∞ | ∞ | ∞ | 17 | 17 | 16 | 16 |
| 7 | ∞ | ∞ | 11 | 11 | 11 | 11 | 11 | 11 | 11 |
| 8 | ∞ | ∞ | ∞ | ∞ | ∞ | 16 | 13 | 13 | 13 |
| 9 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 20 |
したがって、頂点 1 からの頂点 9 の最小距離は 20 です。 そしてその道は
1→3→7→8→6→9
このパスは、先行情報に基づいて決定されます。
ベルマンフォードアルゴリズム
このアルゴリズムは、エッジの重みが負になる可能性のある有向グラフ G =（V、E） の単一ソース最短パス問題を解決します。 さらに、負の加重サイクルが存在しない場合、このアルゴリズムを適用して最短経路を見つけることができます。
Algorithm: Bellman-Ford-Algorithm (G, w, s)
for each vertex v Є G.V
v.d := ∞
v.∏ := NIL
s.d := 0
for i = 1 to |G.V| - 1
for each edge (u, v) Є G.E
if v.d > u.d + w(u, v)
v.d := u.d +w(u, v)
v.∏ := u
for each edge (u, v) Є G.E
if v.d > u.d + w(u, v)
return FALSE
return TRUE分析
最初の for ループは初期化に使用され、 _ O（V）' 回実行されます。 次の for ループが実行されます| * ' V-1 '' | _O（E） *回かかるエッジを通過します。
したがって、Bellman-Fordアルゴリズムは O（V、E） 時間で実行されます。
例
次の例は、Bellman-Fordアルゴリズムが段階的に機能する方法を示しています。 このグラフにはネガティブエッジがありますが、ネガティブサイクルはないため、この手法を使用して問題を解決できます。
初期化時には、ソースを除くすべての頂点に∞のマークが付けられ、ソースには 0 のマークが付けられます。
最初のステップでは、ソースから到達可能なすべての頂点が最小コストで更新されます。 したがって、頂点 a および h が更新されます。
次のステップでは、頂点 a、b、f および e が更新されます。
同じロジックに従って、このステップで頂点 b、f、c および g が更新されます。
ここでは、頂点 c および d が更新されます。
したがって、頂点 s と頂点 d の間の最小距離は 20 です。
先行情報に基づいて、パスはs→h→e→g→c→d
