edmonds算法

1. edmonds-karp算法是如何求最大流的

Edmonds-Karp 算法步骤

每次通过BFS，找到残余网络上从源点到汇点的一条最短增广路

在流网络上增加增广路

修改残余网络，残余容量减去增广路，并添加增广路的反向弧

当无法BFS到增广路时，算法结束

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: ditch
LANG: C++

//对ford算法的改进，变为多项试的。

/*
ID:cmykrgb1
PROG:ditch
LANG:C++
*/
#include<iostream>
#include<fstream>
#defineMAX201
usingnamespacestd;

classTadjl
{
public:
classTnode
{
public:
intr,v;
voidset(inttr,inttv)
{
r=tr;
v=tv;
}
};
intcnt;
Tnodelink[MAX];
};

classtQueue
{
public:
classlinklist
{
public:
linklist*next;
intvalue;
linklist()
{
next=0;
value=0;
}
};
linklist*first,*last;
intsize;
voidadd(intp)
{
if(size==0)
first=last=newlinklist;
else
last=last->next=newlinklist;
last->value=p;
size++;
}
intdel()
{
intrtn=first->value;
linklist*tfirst=first;
first=first->next;
deletetfirst;
size--;
returnrtn;
}
voidreset()
{
size=0;
first=last=0;
}
tQueue()
{
reset();
}
};

ifstreamfi("ditch.in");
ofstreamfo("ditch.out");

Tadjladjl[MAX];
intN,M,ans;

inlineintmin(inta,intb)
{
returna<b?a:b;
}

voidinit()
{
inti,a,b,v;
fi>>N>>M;
for(i=1;i<=N;i++)
{
fi>>a>>b>>v;
adjl[a].link[++adjl[a].cnt].set(b,v);
}
}


intedmonds(intstart,intend)
{
inti,j,k;
intfather[MAX],fp[MAX],max[MAX];
intMaxflow=0;
memset(father,0,sizeof(father));
max[start]=0x7FFFFFFF;
tQueue*Q=newtQueue;
Q->add(start);
while(Q->size)
{
i=Q->del();
for(k=1;k<=adjl[i].cnt;k++)
{
j=adjl[i].link[k].r;
if(!adjl[i].link[k].v||j==start)continue;
if(!father[j])
{
father[j]=i;
fp[j]=k;
max[j]=min(adjl[i].link[k].v,max[i]);
if(j==end)
{
Maxflow+=max[j];
while(father[j])
{
adjl[father[j]].link[fp[j]].v-=max[end];
adjl[j].link[++adjl[j].cnt].set(father[j],max[j]);
j=father[j];
}
memset(father,0,sizeof(father));
Q->reset();
Q->add(start);
break;
}
Q->add(j);
}
}
}
returnMaxflow;
}

voidprint()
{
fo<<ans<<endl;
fi.close();
fo.close();
}

intmain()
{
init();
ans=edmonds(1,M);
print();
return0;
}

2. Hungarain algorithm是什么

Hungarian algorithm

匈牙利算法
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

3. 帮我解释下网络流

必须知识：最短路径问题
1.Dijkstra
适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点v1到所有其他点vj的最短距离；
朴素的Dijkstra算法复杂度为O(N^2)，堆实现的Dijkstra复杂度为O(NlogN).

2.bellman-ford
适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点v1到所有其它点 vj的最短距离。bellman-ford算法复杂度为O(V*E)。

3.Floyed
适用于有负权系数，可以求出图上任意两点之间的最短路径。DP思想的算法，时间复杂度为O(N^3);
for ( k= 1; k<= n; k++)
for ( i= 1; i<= n; i++)
if (graph[i][k]!=INF)
for ( j= 1; j<= n; j++)
if (graph[k][j]!=INF && graph[i][k]+graph[k][j]< graph[i][j])
graph[i][j]= graph[i][k]+ graph[k][j];

NO.1 s-t最大流
两大类算法
1.增广路算法
Ford-Fulkerson算法: 残留网络中寻找增加路径
STEP0：置初始可行流。
STEP1：构造原网络的残量网络，在残量网络中找s－t有向路。如果没有，算法得到最大流结束。否则继续下一步。
STEP2：依据残量网络中的s－t有向路写出对应到原网络中的s－t增广路。对于增广路中的前向弧，置s(e)＝u(e)- f(e)。对于反向弧，置s(e)＝f（e） STEP3：计算crement=min{s（e1），s（e2），…，s（ek）}
STEP4：对于增广路中的前向弧，令f(e)＝f(e)＋crement；对于其中的反向弧，令f(e)＝f(e)-crement，转STEP1。
关键点:寻找可增广路。决定了算法复杂度。
实现：Edmonds-Karp 通过采用了广度优先的搜索策略得以使其复杂度达到O(V*E^2)。

优化—> Dinic算法(*)
Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流。分层的目的是降低寻找增广路的代价。
算法的时间复杂度为O(V^2*E)。其中m为弧的数目，是多项式算法。邻接表表示图，空间复杂度为O(V+E)。

2.预流推进算法
一般性的push-relabel算法: 时间复杂度达到O(V^2*E)。(*)
relabel-to-front算法->改进
最高标号预流推进:时间复杂度O(V^2*sqrt(E))

NO2. 最小费用最大流
求解最小费用流的步骤和求最大流的步骤几乎完全一致，只是在步骤1时选一条非饱和路时，应选代价和最小的路，即最短路。
步骤1. 选定一条总的单位费用最小的路，即要给定最小费用的初始可行流，而不是包含边数最小的路。
步骤2. 不断重复求最大流的步骤来进行，直到没有饱和路存在为止。然后计算每个路的总费用。
和Edmonds-Karp标号算法几乎一样，因为这两种算法都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(V*E^2)。

连续最短路算法 + 线性规划对偶性优化的原始对偶算法(*)
传说中，没见过，据说复杂度是O(V^3)

NO3. 有上下届的最大流和最小流（通过添加点来进行转化）(*)

NO4. 相关图论算法
二分图最大匹配： 加s和t构造最大流
专用算法：hungary算法 O(M*N)

二分图最佳匹配： 加s和t构造最小费用最大流
专用算法：KM算法
朴素的实现方法,时间复杂度为O(n^4)
加上松弛函数O(n^3)

最小路径覆盖：
顶点数－二分图的最大匹配

s-t最小边割集：
最大流最小割定理：最小割等于最大流

普通最小边割集：
Stoer-Wagner Minimum Cut O(n^3)

二分图的最大独立集：
N - 二分图的最大匹配（POJ monthly）girls and boys
反证法证明
普通图的最大独立集是np问题。(*)

4. NP-hard的NP-hard

其中，NP是指非确定性多项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。相应的，若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP困难问题
例如，着名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？
推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！ 这将是个天文数字。
旅行推销员问题是数图论中最着名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。
迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complet或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。
此类问题中，经典的还有 子集和问题； Hamilton回路问题；最大团问题

5. 匈牙利算法 matlab程序出现问题 运行时出现 Undefined function or variable 'a'.

调用 Edmonds 时，忘了个 实际参数 a（有值得）或数值了。
也可以 用默认参数值。
function [Matching,Cost] = Edmonds(a)
if nargin==0
a=.......;
end
Matching = zeros(size(a));
.........

6. 网络流之最大流，您只需判断这个代码是属于哪一种最大流算法即可。

Edmonds - Karp 算法
最简单的增广路类算法，每次用一个 BFS 寻找最短增广路
while(1) 里前半部分的 for 循环就是 BFS 部分，队列 que[] 辅助进行 BFS，找到的增广路存在 pre[i] 中
if(!pre[sink])判断是否存在可到达汇点的增广路，不存在就跳出循环
后半部分 for 循环对找到的路径进行增广操作。

时间复杂度 O(VE^2)，行数虽少，但效率不是很高的算法

最后说一句，这代码风格太差了 = =，只考虑代码长度完全不顾可读性

参考资料是自己的 blog 呵呵

7. 最大流算法中的Edmonds-Karp算法为什么用广度优先搜索增广路径

我花了三个晚上，画了无数的图，试图构造出一个深度遍历之后复杂度会超过ve²，没能成功

然后用了一下午的时间google，最后发现有个国外的论文，研究员通过递归方式构造了一个图，(也就是教科书上那个傻傻的证明e|f|复杂度的五边棱形图，他把这个大棱形对角线那一条边替换成一个小棱形，然后把小棱形的对角线又替换，迭代n次，每个外层大棱形四边的流量，都是内层小棱形四边流量的两倍，也就是说，最里面的小棱形对角线游戏是1，四边流量是1，外面一层的棱形是2，再外面是4，8，16……)

作

8. 求匈牙利算法的原理

对于一个点x和一个点i，如果x和i匹配，那么就匹配；如果i已和j匹配，那么就看j能否和别的点匹配，如果能就可以x和i匹配，匹配数+1。

9. 利用matlab计算多个坐标点，可以互相连接的最短距离

这个问题一般是TSP问题，该回答来自工中号一匹大懒虫
旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中着名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
旅行推销员问题是图论中最着名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。[1]
迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。
此类问题中，经典的还有 子集和问题； Hamilton回路问题；最大团问题。