重みが最小となる閉路を求めるアルゴリズム

グラフグラフ, 有向グラフ, 閉路, 最小値, BFS, ベルマンフォード法, ダイクストラ法

アルゴリズム

最小コストの閉路:

  1. 任意の辺 e = (u,v) について以下を繰り返す
    1. グラフ G から e を取り除く
    2. v から u への最短経路 d を求める(ダイクストラ/BFS など)
    3. d+cost(u,v) を計算する
    4. グラフ G に e を戻す
  2. d+cost(u,v) の最小値が、閉路の重みの最小値

※ ある辺 e を含む最小のコストの閉路を、全ての辺について求めます。

※ 具体例では以下の様になります。

辺 e = (u,v) が使われる閉路のうち、重みが最小となるものは右図のようになります。

e を取り除いたグラフにおいて、u→*vの最短経路は

  • d = 3+2+1 = 6

となり、閉路の最小コストは

  • d+cost(u,v) = 6 + 5 = 11

です。

赤: e, 青: v→uの最短経路

※ このアルゴリズムは無向グラフ・有向グラフの両方に対して使用できます。

※ 重みなしグラフの場合は、辺の重みを 1 として同様のアルゴリズムで求めることができます。

※ コストだけではなく、閉路そのものを求める場合は、経路復元を行えば良いです(ダイクストラ法を参照)。

計算量

  • 重み付きグラフ(負の辺あり)の場合: \(O(E(EV))\)
  • 重み付きグラフ(負の辺なし)の場合: \(O(E(E \log V))\)
  • 重みなしグラフの場合: \(O(E(E + V))\)

最短経路を求めるアルゴリズムによって計算量が異なります。

コストが負の辺が含まれている場合は、ベルマンフォード法などを用いる必要があるので、最短距離を求めるのに一回あたり \(O(EV)\) だけかかります。

負の辺が含まれていない場合は、ダイクストラ法を用いることができるので、一回あたり \(O(E \log V)\) となります。

重みなしグラフの場合は、幅優先探索(BFS) で最短距離を \(O(E+V)\) で求めることが可能です。

実装例

以下は最短距離を求めるのにダイクストラ法を用いた場合の実装例です。

練習問題

  • [AtCoder] ABC 142 F – Pure:重みが無い場合なのでBFSで最短距離が求まりますが、高速な言語ならダイクストラ法でも間に合います