フォードファルカーソン法をRubyで実装 - yasuhisa's blogグラフに対する基本的な問題として 最小全域木 最短路問題 最大フロー の3つがあると思う。で、最小全域木は離散最適の課題としてPrim法を使って解いてみたし、最短路問題はベルマンフォードのアルゴリズムをRubyとC++で解いてみた。となったら、最大フローを実装しないわけにはいかないな、ということでフォードファルカーソン法を実装してみました。上の3つの問題では一番ややこしかった気がする。というわけでコードと実行結果。 繰り返しの中で残余ネットワークを更新していって、残余ネットワークにおいて始点から終点へのパスが存在するかを幅優先探索を使って探索していくという流れ。 # -*- coding: utf-8 -*- require "pp" class DirectedGraph attr_reader :nodes attr_reader :weights attr_reader :edges
