きままにものづくり

日々の気付いたことなんかを書いてます。

フォード-ファルカーソン

フォード-ファルカーソン法は、最小フロー問題を解くアルゴリズムのひとつである。

目次

  1. アルゴリズムの説明
  2. 計算量
  3. コード

アルゴリズムの説明

このアルゴリズムを説明する前に、残余ネットワークの説明をする。残余ネットワークとは、現状での流すことができる量をコストとした有向グラフのことである。
以下の図を例にとる。左の図は、ネットワークフローを示す。辺に書いてある数字は、現在流してる量/許容量を示す。この時の残余ネットワークは右の図になる。
茶色の数字と黒い数字を足した値が許容量となり、黒い数字が現在流している量を示す。
f:id:even_eko:20130808195805p:plain

フォードファルカーソン法では、残余ネットワークを用いて最適解を導く。

  1. ネットワークフローから残余ネットワークを作成する。
  2. 残余ネットワークにおいて、SからTへ向かうルートがあるか探索する。ルートが存在しない場合は、終了する。
  3. 残余ネットワークを用いて、SからTへの最大流量を求める。
  4. 3の結果を反映させた新しいネットワークフローを作成し、1の処理に戻る。

この流れを図を用いて、説明していく。
f:id:even_eko:20130808195935p:plain
まず、左のネットワークフローから残余ネットワークを作成する。
この中で、SからTへと向かうことのできるルートを探索する。
この場合では、点線で示したルートを辿ることができる。
このルートの中で、最小のコストがこのルートの最大流量となる。
この値を用いて新たな、ネットワークフローを作成する。
f:id:even_eko:20130808195941p:plain
新しく作成したネットワークフローから、残余ネットワークを作成する。
残余ネットワークにおいて、SからTへと向かうルートが存在するので、先ほどと同様の処理を行う。
f:id:even_eko:20130808195950p:plain
まだ、ルートが存在するので先ほどと同様の処理を行う。
f:id:even_eko:20130808195957p:plain
残余ネットワークにおいて、SからTへ向かうルートが存在しなくなった。
よって、これが最大流となる。
この処理では、ずっと青いルートを辿ってきたので残余ネットワークの必要性が感じられないかもしれない。
残余ネットワークの必要性を確認するために、違うルートを辿る。

前回の処理では、初めにS->A->B->Tというルートを辿った。
次の処理では、初めにS->A->C->Tというルートを辿る。
f:id:even_eko:20130808200004p:plain
S->A->C->Tというルートでの最大流量は5なので、5を流す。
f:id:even_eko:20130808200020p:plain
次に、S->A->B->Tというルートを辿り、5を流す。
f:id:even_eko:20130808200027p:plain
ここで、青いルートではSからTへと行けなくなった。
しかし、茶色のルートを用いることでS->C->A->B->Tと辿れる。
f:id:even_eko:20130808200036p:plain
茶色のルートでは、青とは逆の計算になることを注意して、ネットフロー図を作成する。
これは、前回の処理の結果と同じになる。

このように、残余ネットワークを用いることで最大流量を求めることができる。

計算量

残余ネットワークにおいてSからTへのルートがあるのなら、流量は必ず増加する。最大流量をFとすると、たかだかF回の深さ優先探索を実行することになる。深さ優先探索はメモ化をしながら探索するので、エッジをEとおくと、たかだかE回の探索で済む。
よって、計算量は
O(F|E|)
となる。

コード

#include <vector>
#include <iostream>
 
using namespace std;
 
#define MAX_V 50
#define INF (1<<20)
 
//to:行き先,cap:容量,rev:逆(G[e.to][e.rev]で逆辺の構造体にアクセスできる。)
struct edge {
  int to,cap,rev;
};
 
vector<edge> G[MAX_V];
bool used[MAX_V];
 
//辺を追加。revは,相互参照できるようにしている。sizeで実現しているが、別のルールを用いても良い(i.e ハッシュ)。逆辺の逆辺は通常の辺である。
void
add_edge(int from,int to,int cap)
{
  G[from].push_back( (edge){ to,cap,(int)G[to].size() } );
	G[to].push_back( (edge){ from,0,(int)G[from].size()-1});
}
 
//sからtへ移動可能ならそのルートの最大流量を返し、不可能なら0を返す。
int
dfs(int v,int t,int f)
{
	if (v==t)
		return f;
	used[v] = true;
	for (int i=0; i<G[v].size(); ++i) {
		edge &e = G[v][i];
		if (!used[e.to] && e.cap>0) {
			int d = dfs(e.to, t, min(f,e.cap));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
 
//sからtへの最大流量を返す。
int
max_flow(int s,int t)
{
	int flow = 0;
	for (;;) {
		memset(used, 0, sizeof(used));
		int f = dfs(s, t, INF);
		if (f==0) {
			return flow;
		}
		flow += f;
	}
}
 
int
main()
{
	vector<vector<int> >  to =
	{
		{1,3},
		{2,3},
		{3,4},
		{4}
	}
	;
	vector<vector<int> > cap =
	{
		{10,2},
		{6,6},
		{3,8},
		{5}
	}
	;
	for (int i=0; i<to.size(); ++i) {
		for (int j=0; j<to[i].size(); ++j) {
			add_edge(i, to[i][j], cap[i][j]);
		}
	}
	cout << max_flow(0, 4) << endl;
}