图论-网络流

温安适

发布于 2018-05-17 17:02:34

1.2K0

发布于 2018-05-17 17:02:34

文章被收录于专栏：温安适的blog温安适的blog

前言

大家好，祝大家2017年身体健康，万事如意，开年第一篇blog网路流，希望大家指正。

网路流问题介绍

描述

设给定有向图G=(V,E),其边的容量为cvw.（这些容量可以代表通过一个管道的水的流量或者马路上的交通流量） s为发点，t为收点，最大网络流问题是求从s到t可以通过的最大流量。

性质

在既不是发点s，也不是收点t的任意顶点v，总的进入流必须等于总的发出流。

实际应用举例

最大网络流可以解决二分匹配问题.

二分匹配问题定义

找出E的最大子集E`使得没有顶点含在多于一条的边中。

图解说明

生活中二分匹配问题举例

有一组老师，有一些课，以及每位老师有资格教授的课程表，如果每位老师最多只能开设一门课，那么最多可以开设几门课？

如何转换问题

以老师（例如下图绿色），课程（下图蓝色）为节点。
以课程列表中的老师与课程关系构建图，并将每条边的权赋值为1
创建虚拟节点s，t。s到每个老师有一条权为1的边，每个课程有一条权为1到t的边。

如下图所示：该问题实际为从s到t的最大网络流。

网络流问题算法实现

语言描述

以Dijkstra算法，求解从s到t的赋权最短路径。
找到当前最短路径上的最小权，即为当前最大网络流。
以当前最短路径和当前最大网络流，修改原图为残余图，保存当前最大网络流。
以残余图继续执行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);
		}
	}