最大フロー問題とFord-Fulkersonアルゴリズム

最大フロー問題は、ネットワークにおいて、あるソースからシンクへ流すことができる最大の流量を求める問題です。この問題は、さまざまな実世界のシナリオ（例えば、交通網、通信ネットワークなど）に適用されます。Ford-Fulkersonアルゴリズムは、この最大フローを求めるための基本的なアルゴリズムの一つです。

最大フロー問題の定義

ネットワークは、ノード（点）とエッジ（辺）で構成され、各エッジには流量制限（容量）が設定されています。最大フロー問題では、以下の要素があります。

• ソース（s）：流れの出発点
• シンク（t）：流れの終点
• 容量（capacity）：各エッジに設定された最大流量

Ford-Fulkersonアルゴリズムの概要

Ford-Fulkersonアルゴリズムは、以下の手順で最大フローを計算します。

1. 初期フローを0に設定する。
2. 増加パス（ソースからシンクへのパス）を見つける。このパスは、各エッジの残余容量が正の値を持つ必要があります。
3. 増加パスの最小の残余容量を求める。
4. この容量だけフローを増加させ、エッジの残余容量を更新する。
5. 増加パスが見つからなくなるまで、2〜4を繰り返す。
6. 最終的なフローが最大フローとなります。

実装

以下に、PythonでのFord-Fulkersonアルゴリズムの実装例を示します。

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # グラフの頂点数
        self.graph = [[0] * vertices for _ in range(vertices)]  # 隣接行列

    def add_edge(self, u, v, w):
        self.graph[u][v] = w  # 辺(u, v)に容量wを設定

    def bfs(self, s, t, parent):
        visited = [False] * self.V  # 訪問済みのノード
        queue = [s]  # BFSのキュー
        visited[s] = True

        while queue:
            u = queue.pop(0)

            for v in range(self.V):
                if not visited[v] and self.graph[u][v] > 0:  # 残余容量がある
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u  # 親ノードを記録

                    if v == t:
                        return True  # シンクに到達

        return False  # シンクに到達できなかった

    def ford_fulkerson(self, source, sink):
        parent = [-1] * self.V  # 増加パスを記録する配列
        max_flow = 0  # 最大フローの初期値

        while self.bfs(source, sink, parent):  # 増加パスが見つかる限り
            path_flow = float('Inf')  # パスの流量を無限大に初期化
            v = sink

            while v != source:  # ソースに戻るまで
                u = parent[v]
                path_flow = min(path_flow, self.graph[u][v])  # 残余容量の最小値を取得
                v = parent[v]

            # フローを更新
            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow  # 正方向の残余容量を減少
                self.graph[v][u] += path_flow  # 逆方向の残余容量を増加
                v = parent[v]

            max_flow += path_flow  # 最大フローを更新

        return max_flow

# 使用例
g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 1, 4)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source = 0  # ソース
sink = 5    # シンク
print("最大フローは:", g.ford_fulkerson(source, sink))

コードの解説

1. Graphクラス: グラフを表すクラスで、頂点数と隣接行列を初期化します。add_edgeメソッドでエッジを追加します。
2. bfsメソッド: 幅優先探索を用いてソースからシンクへの増加パスを探索します。親ノードを記録し、シンクに到達すればTrueを返します。
3. ford_fulkersonメソッド: 最大フローを計算するメインメソッドです。BFSで増加パスを見つけ、流量を更新します。
4. 使用例: グラフを作成し、エッジを追加します。ford_fulkersonメソッドを呼び出して最大フローを計算します。

このアルゴリズムは、単純でありながら強力です。様々な問題に応用できるため、ネットワークフロー問題を学ぶ上で非常に重要です。