Upgrade to Pro — share decks privately, control downloads, hide ads and more …

グラフアルゴリズムその2: 単一始点最短路問題 /graphShortestPaths

グラフアルゴリズムその2: 単一始点最短路問題 /graphShortestPaths

Miyakawa Taku

January 29, 2018
Tweet

More Decks by Miyakawa Taku

Other Decks in Programming

Transcript

  1. 最短路問題の分類  単一始点最短路問題:  始点sから各頂点への最短路を求める  単一目的地最短路問題:  各頂点から目的地tへの最短路を求める 

    本質的には単一始点最短路問題と同じ  単一点対最短路問題:  ある頂点対(u, v)間の最短路を求める  uを始点とする単一始点最短路問題の部分問題  全点対最短路問題:  すべての頂点対(u, v)間の最短路を求める 4/42
  2. データ構造 頂点 = { Pred: (暫定)最短路で1つ手前の頂点 Dist: (暫定)最短路で始点からの距離 } //

    探索が終わった時点で、暫定でなくなる 辺 = { From: 矢羽側の頂点 To: 矢尻側の頂点 Weight: 辺重み } 9/42
  3. Bellman-Fordアルゴリズム 始点のDistを0に、始点以外のDistを∞に設定 loop (頂点の数 - 1) 回: // ← なんで?

    for すべての辺(From To Weight): D = From.Dist + Weight if D が To.Distよりも短ければ: Toを更新: .Pred=From .Dist=D endif endfor endloop この時点でFrom.Dist+Weight < To.Dist となる辺があれば、グラフは負閉路を含んでいる 10/42
  4. 例題 c d e b a S 1 2 1

    4 6 1 2 3 11/42
  5. ループ1: d→a ∞ ∞ ∞ ∞ ∞ 0 1 2

    1 4 6 1 2 3 変更なし ※From側のDistが∞だから 13/42
  6. ループ1: c→b ∞ ∞ ∞ ∞ ∞ 0 1 2

    1 4 6 1 2 3 変更なし 14/42
  7. ループ1: c→d ∞ ∞ ∞ ∞ ∞ 0 1 2

    1 4 6 1 2 3 変更なし 15/42
  8. ループ1: b→d ∞ ∞ ∞ ∞ ∞ 0 1 2

    1 4 6 1 2 3 変更なし 16/42
  9. ループ1: a→c ∞ ∞ ∞ ∞ ∞ 0 1 2

    1 4 6 1 2 3 変更なし 17/42
  10. ループ1: S→a ∞ ∞ ∞ ∞ 1 0 1 2

    1 4 6 1 2 3 変更: ∞→1 18/42
  11. ループ1: S→b ∞ ∞ ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更: ∞→1 19/42
  12. ループ1: S→c 6 ∞ ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更: ∞→6 20/42
  13. ループ2: d→a 6 ∞ ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更なし 21/42
  14. ループ2: c→b 6 ∞ ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更なし 22/42
  15. ループ2: c→d 6 7 ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更: ∞→7 23/42
  16. ループ2: b→d 6 5 ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更: 7→5 24/42
  17. ループ2: a→c 3 5 ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更: 6→3 25/42
  18. ループ2: S→a 3 5 ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更なし 26/42
  19. ループ2: S→b 3 5 ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更なし 27/42
  20. ループ2: S→c 3 5 ∞ 1 1 0 1 2

    1 4 6 1 2 3 変更なし 28/42
  21. ループ5終了時点 3 4 ∞ 1 1 0 1 2 1

    4 6 1 2 3 観察:  各頂点に、0/1個のpredが設定されている  最短路の部分経路もまた最短路である 29/42
  22. Bellman-Fordアルゴリズム 始点のDistを0に、始点以外のDistを∞に設定 loop (頂点の数 - 1) 回: // ← なんで?

    for すべての辺(From To Weight): D = From.Dist + Weight if D が To.Distよりも短ければ: Toを更新: .Pred=From .Dist=D endif endfor endloop この時点でFrom.Dist+Weight < To.Dist となる辺があれば、グラフは負閉路を含んでいる 30/42
  23. 繰り返し回数の直感的理解  頂点の数だけが与えられている場合、 最短路の辺の数は高々(頂点数-1) 例: 6頂点(S, a, b, c, d,

    e)→5辺  (頂点数-1)回だけ繰り返せば、すべての 最短路のすべての辺がたどられるはず 31/42
  24. Bellman-Fordアルゴリズム 始点のDistを0に、始点以外のDistを∞に設定 loop (頂点の数 - 1) 回: for すべての辺(From To

    Weight): D = From.Dist + Weight if D が To.Distよりも短ければ: Toを更新: .Pred=From .Dist=D endif endfor endloop この時点でFrom.Dist+Weight < To.Dist となる辺があれば、グラフは負閉路を含んでいる 計算量: O(頂点数*辺数) 32/42
  25. データ構造 頂点 = { Pred: (暫定)最短路で1つ手前の頂点 Dist: (暫定)最短路で始点からの距離 Neibors: (矢印の先の頂点,

    重み)の集合 } 頂点の優先度付きキュー = { extractMin(): 距離が最も小さい頂点を抜き出す decreaseKey(V, Dist): 頂点Vの距離を更新する } // 距離を優先度とする 34/42
  26. Dijkstraのアルゴリズム 始点のDistを0に、始点以外のDistを∞に設定 Q = すべての頂点を含む優先度付きキュー while Qが空でない間: Min = Q.extractMin()

    for すべてのMin.neibors → (V, Weight) : D = Min.dist + Weight if DがV.distよりも短ければ: Vを更新: .Pred=Min .Dist=D Q.decreaseKey(V, D) endif endfor endwhile 35/42
  27. 直感的な理解 最短路と距離が確定した頂点の集合S 最短路と距離が未確定の頂点の集合Q Qの 中 の 頂 点 は 最短路が未確定

    Sの中の頂点から来る 道があれば、 そのいずれかが 暫定最短路として 設定されている 37/42
  28. Dijkstraのアルゴリズムの計算量 始点のDistを0に、始点以外のDistを∞に設定 Q = すべての頂点を含む優先度付きキュー while Qが空でない間: Min = Q.extractMin()

    for すべてのMin.neibors → (V, Weight) : D = Min.dist + Weight if DがV.distよりも短ければ: Vを更新: .Pred=Min .Dist=D Q.decreaseKey(V, D) endif endfor endwhile 頂 点 数 回 実 行 さ れ る だ い た い 辺 数 回 実 行 さ れ る 41/42
  29. Dijkstraのアルゴリズムの計算量 優先度付きキューの操作の計算量に依存 優先度付き キューの実装 extractMin decrease Key Dijkstraの計算量 2 分ヒープ

    Θ(log N) Θ(log N ) Θ(辺数* log頂点数 +頂点数* log頂 点 数) フィボナッチ ヒープ Θ(log N) Θ(1) ※ならし Θ(辺数 +頂点数* log頂 点 数) ※ならし 計算量は漸近的にフィボナッチヒープが有利 フィボナッチヒープの実装は複雑、 2分ヒープは単純なので、 グラフが小さい場合は 2分ヒープを使う方が有利 42/42 ※N = 優先度付きキューの要素数