DAA-最短経路

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

ダイクストラのアルゴリズムは、有向加重グラフG =(V、E)で単一ソースの最短経路問題を解きます。ここで、すべてのエッジは非負です(つまり、各エッジ(u、v に対してw(u、v) ≥0 )Є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(V2 + E)

このアルゴリズムでは、min-heapを使用すると Extract-Min() 関数はからノードを返すように動作します Q 最小のキーを使用すると、このアルゴリズムの複雑さをさらに軽減できます。

頂点について考えてみましょう 1 そして 9それぞれ開始頂点と宛先頂点として。最初に、開始頂点を除くすべての頂点は∞でマークされ、開始頂点はでマークされます。0

バーテックス 初期 ステップ1V 1 ステップ2V 3 ステップ3V 2 ステップ4V 4 ステップ5V 5 ステップ6V 7 ステップ7V 8 ステップ8V 6
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

したがって、頂点の最小距離 9 頂点から 1 です 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) 回。

したがって、ベルマンフォードアルゴリズムはで実行されます O(V, E) 時間。

次の例は、ベルマンフォードアルゴリズムがどのように機能するかを段階的に示しています。このグラフには負のエッジがありますが、負のサイクルはありません。したがって、この手法を使用して問題を解決できます。

初期化時に、ソースを除くすべての頂点は∞でマークされ、ソースはでマークされます。 0

最初のステップでは、ソースから到達可能なすべての頂点が最小コストで更新されます。したがって、頂点a そして h 更新されます。

次のステップでは、頂点 a, b, f そして e 更新されます。

同じロジックに従って、このステップでは頂点 b, f, c そして g 更新されます。

ここでは、頂点 c そして d 更新されます。

したがって、頂点間の最小距離 s および頂点 d です 20

先行情報に基づくと、パスはs→h→e→g→c→dです。