http://yuanhuixie.blogcn.com/
流网络G=(V,E)是一个有向图,每一条边都有一非负容量 c(u,v)>=0.流网络中有两个特殊的点:源点 s 和汇点 t 。
最大流问题中,给出一个具有源点和汇点的流网络,希望找出从源点到汇点的最大值流。
解决最大流问题的 Ford-Fulkerson 方法依赖于三种重要的思想:残留网络、增广路径和割。
Ford-Fulkerson是一种迭代的方法,通过更新有边相连的每对顶点 u,v之间的网络流 f[u,v],来计算出图 G=(V,E)中的最大流。
class Link
{
public int key;
public int c;
public Link next;
public int Key
{
get
{ return key; }
set
{ key = value; }
}
public int C
{
get
{ return c; }
set
{ c = value; }
}
public Link Next
{
get
{ return next; }
set
{ next = value; }
}
public Link()
{
key = 0;
c = 0;
next = null;
}
public int Min() //返回残余容量
{
Link R=this.Next;
int min = this.C;
while (R != null)
{
if (min > R.C)
min = R.C;
R = R.Next;
}
return min;
}
}
public int[,] Ford_Fulkerson(int[,] G, int s, int t)
{
int c = 0;
Link P = new Link(); //P用于表示图 G 的一条增广路径。
int[,] f = new int[G.Length, G.Length];
for(int i=0;i<G.Length;i++)
for (int j = 0; j < G.Length; j++)
{
if (G[i, j] != 0) //如果(u,v)是图G的边,把那条边的流值初始化为0
{
f[i, j] = 0;
f[j, i] = 0;
}
}
while ((P = ExistPath(G))!=null) //这里判断图 G中是否有残余流网络,此函数可以用广度优先搜索,但是我还是没写好
{
c = P.Min(); //取出增广路径的残余容量 c
while(P.Next!=null)
{
f[P.Key, P.Next.Key] += c;
f[P.Next.Key, P.Key] = 0 - f[P.Key, P.Next.Key];
P = P.Next;
}
}
return f;
}
昨天写了最大流里面的 Ford-Fulkerson 算法,但是里面有个寻找函数 ExistPath(int[,] G, int s, int t, int[,] f) 我没写出来,今天写好了,现在再发一次:
public int[,] Ford_Fulkerson(int[,] G, int s, int t)
{
int c = 0;
Link P = new Link(); //P用于表示图 G 的一条增广路径。
int[,] f = new int[G.Length, G.Length];
for (int i = 0; i < G.Length; i++)
for (int j = 0; j < G.Length; j++)
{
if (G[i, j] != 0) //如果(u,v)是图G的边,把那条边的流值初始化为0
{
f[i, j] = 0;
f[j, i] = 0;
}
}
while ((P = ExistPath(G, s, t, f)) != null) //这里判断图 G中是否有残余流网络,返回增广路径
{
c = P.Min(); //取出增广路径的残余容量 c
while (P.Next != null)
{
f[P.Key, P.Next.Key] += c;
f[P.Next.Key, P.Key] = 0 - f[P.Key, P.Next.Key];
P = P.Next;
}
}
return f;
}
public Link ExistPath(int[,] G, int s, int t, int[,] f)
{
int j = s, k = 0, Next = 0;
int[] Pass = new int[G.Length];
for (int i = 0; i < G.Length; i++)
Pass[i] = -1;
Pass[k] = s; //用 Pass[] 记下遍历过程中经过的节点的顺序
Link L2 = new Link();
Link L = L2;
for (int i = 0; i < G.Length; i++)
{
if ((Next = NextNode(G, Pass, j)) != -1)
Pass[k++] = Next;
j = Next;
if (Next == t) //当到达汇点时就停止
break;
}
for (int i = 0; i < G.Length; i++)
{
L2.Key = Pass[i];
L2 = L2.Next;
if (Pass[i] == t) //当搜索过程中有到达汇点的就表示存在有增广路径
{
L2.Key = Pass[i];
return L;
}
}
return null;
}
public int NextNode(int[,] G, int[,] Pass, int j)
{
for (int i = 0; i < G.Length; i++)
{
if (Pass[i] == -1) //当节点没有被经过
{
if (G[j, i] != 0 && f[j, i] != G[j, i]) //当边(j,i)存在 且有残余容量时
{
return i;
}
}
}
return -1;
}
分享到:
相关推荐
最大流算法是图论中的一个重要概念,用于确定在有向图中从源点到汇点的最大可能流量。这种算法在很多领域都有应用,比如网络设计、运输问题、电路理论等。在本例中,我们讨论的是如何使用MATLAB来实现最大流算法。 ...
### 最大流高级算法 #### 一、引言与背景 在计算机科学和运筹学领域,最大流问题(Maximum Flow Problem)与最小割问题(Minimum Cut Problem)是两个极其重要且被广泛研究的问题。这类问题的核心在于寻找图中源点...
最小费用最大流问题在计算机科学和运筹学中是一个重要的网络优化问题,它结合了最大流问题和最小费用路径问题。在实际应用中,比如物流配送、电力传输、通信网络等场景,我们不仅关心能够通过网络传递的最大流量,还...
最大流问题和云计算框架的结合是近年来计算机科学领域研究的热点之一,它主要关注在给定网络中找到从源点到汇点的最大流量路径。这一问题在交通规划、网络设计、资源分配等多个实际场景中有广泛的应用。最大流问题的...
最大流 转换流。 比{mu,min}stache更快更简单。 安装 $ npm install maxstache-stream 用法 const maxstache = require ( 'maxstache-stream' ) const fs = require ( 'fs' ) fs . createReadStream ( './foobar....
然后,求出这个图的最大流,如果最大流等于∑downi,那么就是可行流,否则没有可行流。 有源汇的上下界网络流: 在有源汇的上下界网络流中,可以通过添加一条 t->s 的边,流量限制为[0, inf],将其转换为无源汇...
"超酷堆叠相片转瀑布流网格布局动画"是一种创新且吸引用户的网页设计技术,它将静态的图片堆栈转变为动态的瀑布流布局,为用户提供流畅且富有吸引力的浏览体验。这种布局方式通常用于图片展示类网站,如摄影、电商或...
为了简化问题,本文提出了使用最小费用最大流算法,并证明了这种方法的高效性。 在最小费用最大流问题中,我们的目标是找到一个网络中的最大流量,同时使得流量的成本最小化。这在实际问题中尤为关键,因为不仅要...
每个循环通常由一个最大值和一个最小值(即峰和谷)组成。 7. **结果分析**:统计不同幅度和寿命的循环数量,绘制循环图,这可能涉及`histcounts()`或`bar()`函数。 8. **循环对寿命的评估**:基于提取的循环,...
最终,输出的结果可能包括最大温差、最小温差、平均温差、循环次数等,这些信息有助于评估IGBT的热疲劳状况,从而为器件的热管理和寿命预测提供依据。 需要注意的是,雨流计数法的应用需结合实际的热模型和材料的...
7. **最大流最小割定理**:网络中的最大流等于最小割的大小,这是网络流理论的基础定理。 在"线性规划与网络流24题"中,我们可以学习如何将线性规划问题转换为网络流问题,因为很多线性规划问题可以自然地用网络流...
5. **`mark(int readlimit)`方法**:用于在流中设置一个标记,`readlimit`参数定义了从该标记开始可以读取的最大字节数,超过此限制标记将失效。 6. **`read()`方法**:这是输入流中最核心的方法,用于从流中读取一...
接下来,采用特定算法寻找最小闭合路径,即构成一个完整的应力-应变循环的路径,这个循环的边界由一对最大值和最小值决定。每个找到的循环代表一次应力-应变的完整变化,从而可以计算对应的疲劳损伤。 雨流计数法与...
在示例代码中,用err变量记录每次迭代的误差,当误差达到足够小或达到最大迭代次数时停止计算。 通过以上步骤,我们可以使用MATLAB编程实现对二维方腔内不可压缩流体的流函数-涡量法数值模拟,从而理解和分析流动...
HEVC引入了更多的编码工具,如更精细的块划分(最大支持64x64像素)、多参考帧预测、熵编码优化等,这些都极大地提高了压缩性能。 在给定的文件列表中,`video-hvec-h265.mkv`和`video-hvec-h265-lp.mp4`表明了两个...
- `setReadTimeout()`:设置读取超时时间,即从连接中读取数据的最大等待时间。 - `setFollowRedirects()`:设置是否自动跟随重定向,默认为`true`。 - `setRequestMethod()`:设置请求方式,如“GET”或“POST”。 ...
该文档涵盖了网络流算法的核心概念,包括最大流问题、最小费用流问题、运输问题以及二部图匹配等问题的介绍与分析。 在最大流问题(Max-Flow Problem)中,一个流网络可以被想象成许多输水管道,其中每个管道代表...
1. **转矩控制**:通过改变转子侧电流,调节发电机转矩,使风力机在最佳叶尖速度附近运行,最大化风能捕获。 2. **功率控制**:定子侧逆变器控制电网侧的功率输出,以适应电网需求,确保功率平稳输送。 3. **电压...