网路流问题介绍
描述
设给定有向图G=(V,E),其边的容量为cvw.（这些容量可以代表通过一个管道的水的流量或者马路上的交通流量） s为发点，t为收点，最大网络流问题是求从s到t可以通过的最大流量。
性质
在既不是发点s，也不是收点t的任意顶点v，总的进入流必须等于总的发出流。
实际应用举例
最大网络流可以解决二分匹配问题.
二分匹配问题定义
找出E的最大子集E`使得没有顶点含在多于一条的边中。
图解说明
生活中二分匹配问题举例
有一组老师，有一些课，以及每位老师有资格教授的课程表，如果每位老师最多只能开设一门课，那么最多可以开设几门课？
如何转换问题
1、 以老师（例如下图绿色），课程（下图蓝色）为节点。
2、 以课程列表中的老师与课程关系构建图，并将每条边的权赋值为1
3、 创建虚拟节点s，t。s到每个老师有一条权为1的边，每个课程有一条权为1到t的边。
如下图所示：该问题实际为从s到t的最大网络流 。
网络流问题算法实现
语言描述
1、 以Dijkstra算法，求解从s到t的赋权最短路径。
2、 找到当前最短路径上的最小权，即为当前最大网络流。
3、 以当前最短路径和当前最大网络流，修改原图为残余图，保存当前最大网络流。
4、 以残余图继续执行1,2,3步，直到s和t不连通为止。
图例说明最大网络流算法
代码示例
/**
* 获取从起点到终点的最大网络流
* @param start 起点
* @param end 终点
* @return 从起点到终点的最大网络流
*/
public Integer getMaxFlow(Vertex start,Vertex end){
int maxFlow=0;
while (true) {
dijkstra(start, end);//找到从起点到终点的最短路径
if(end.dist==Integer.MAX_VALUE){
break;
}
printPath(end);//打印路径便于观察
int currentMaxFlow = getCurrentMaxFlow(end);//得到当前路径的最大网络流
//修建原图
changeGraphWeightAndSetMaxFlow(end, currentMaxFlow, maxFlowGraph);
maxFlow+=currentMaxFlow;//记录最大网络流
//打印当前最大网络流图，以便追踪是否正确
System.out.println();
for (Vertex v : maxFlowGraph.values()) {
System.out.println(v);
}
}
return maxFlow;
}
1、获取当前最短路径的最大流
/**
* 获取当前最短路径的最大流
* @param end 终点
* @return 从起点到终点的当前最大流
*/
private Integer getCurrentMaxFlow(Vertex end) {
if (end.getPath() != null) {
Integer parentcwv = 0;
if (end.getPath() != null) {
parentcwv = getCurrentMaxFlow(end.getPath());
}
Integer cwv = end.getPath().getAdj().get(end);
return Math.min(cwv, parentcwv);
} else {
return Integer.MAX_VALUE;
}
}
2、修改原图为残余图保留当前网络流
/**
* 为网络流图赋值，修剪原图
* 如果原图中有一条边修剪后权为0，去掉该边
* @param end 终点
* @param currentMaxFlow 当前最大流
* @param maxFlowGraph 网络流结果图
*/
public void changeGraphWeightAndSetMaxFlow(Vertex end, Integer currentMaxFlow, Map<String, Vertex> maxFlowGraph) {
if (end.getPath() != null) {
int oldCwv = end.getPath().getAdj().get(end);
if (oldCwv - currentMaxFlow > 0) {
end.getPath().getAdj().put(end, oldCwv - currentMaxFlow);
} else if (oldCwv - currentMaxFlow == 0) {
end.getPath().getAdj().remove(end);
}
String startName=end.getPath().name;
Integer oldcvw=maxFlowGraph.get(startName).adj.get(maxFlowGraph.get(end.name));
maxFlowGraph.get(startName).adj.put(maxFlowGraph.get(end.name), oldcvw+currentMaxFlow);
maxFlowGraph.get(end.name).setPath(maxFlowGraph.get(startName));
changeGraphWeightAndSetMaxFlow(end.getPath(), currentMaxFlow, maxFlowGraph);
}
}
完整代码地址
[码云地]址：单击跳转](git.oschina.net/WLjava/Data…)