Ford-Fulkerson方法在矩阵上实现

Ford—Fulkerson法是网络极值中的最大流问题的一种基本有效的算法。最大流问题在包含流量问题的系统中有着广泛的应用,例如在公路系统中的车流、控制系统中的信息流、金融系统中的现金流等等都有最大流问题。而目前介绍Ford—Fulkerson方法的资料中都是在网络图上进行的,这样很难在计算机上实现。本文将引进一个容量矩阵,把Ford—Fulkerson方法在容量矩阵上实现,这样Ford—Fulker法易缩制成程序在计算机上实现。 一、问题提出与算法思路 设有向图G=(V,E),V是所有顶点的集合,E是所有弧的集合,C_(ij)为有向图G中的弧(V_i,V_j)∈E的最大容量。为简单起见,不妨设有向图G中只有一个起点V_1和只有一个