- 浏览: 1654222 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (405)
- C/C++ (16)
- Linux (60)
- Algorithm (41)
- ACM (8)
- Ruby (39)
- Ruby on Rails (6)
- FP (2)
- Java SE (39)
- Java EE (6)
- Spring (11)
- Hibernate (1)
- Struts (1)
- Ajax (5)
- php (2)
- Data/Web Mining (20)
- Search Engine (19)
- NLP (2)
- Machine Learning (23)
- R (0)
- Database (10)
- Data Structure (6)
- Design Pattern (16)
- Hadoop (2)
- Browser (0)
- Firefox plugin/XPCOM (8)
- Eclise development (5)
- Architecture (1)
- Server (1)
- Cache (6)
- Code Generation (3)
- Open Source Tool (5)
- Develope Tools (5)
- 读书笔记 (7)
- 备忘 (4)
- 情感 (4)
- Others (20)
- python (0)
最新评论
-
532870393:
请问下,这本书是基于Hadoop1还是Hadoop2?
Hadoop in Action简单笔记(一) -
dongbiying:
不懂呀。。
十大常用数据结构 -
bing_it:
...
使用Spring MVC HandlerExceptionResolver处理异常 -
一别梦心:
按照上面的执行,文件确实是更新了,但是还是找不到kernel, ...
virtualbox 4.08安装虚机Ubuntu11.04增强功能失败解决方法 -
dsjt:
楼主spring 什么版本,我的3.1 ,xml中配置 < ...
使用Spring MVC HandlerExceptionResolver处理异常
算法导论对最大流算法有很详细的介绍,今天实现了最大流Ford-Fulkerson的算法,包括BFS和DFS来搜索增广路径。
输入:
6 10 // 6 nodes, 10 edges
0 1 16 // capacity from 0 to 1 is 16
0 2 13 // capacity from 0 to 2 is 13
1 2 10 // capacity from 1 to 2 is 10
2 1 4 // capacity from 2 to 1 is 4
3 2 9 // capacity from 3 to 2 is 9
1 3 12 // capacity from 1 to 3 is 12
2 4 14 // capacity from 2 to 4 is 14
4 3 7 // capacity from 4 to 3 is 7
3 5 20 // capacity from 3 to 5 is 20
4 5 4 // capacity from 4 to 5 is 4
输出:
23
这个算法广度和深度优先遍历都是一样的,写了两种
是啊,代码下面有输入输出实例:
输入:
6 10 // 6 nodes, 10 edges
0 1 16 // capacity from 0 to 1 is 16
0 2 13 // capacity from 0 to 2 is 13
1 2 10 // capacity from 1 to 2 is 10
2 1 4 // capacity from 2 to 1 is 4
3 2 9 // capacity from 3 to 2 is 9
1 3 12 // capacity from 1 to 3 is 12
2 4 14 // capacity from 2 to 4 is 14
4 3 7 // capacity from 4 to 3 is 7
3 5 20 // capacity from 3 to 5 is 20
4 5 4 // capacity from 4 to 5 is 4
输出:
23
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class MaxFlow { private int capacity[][]; private int flow[][]; private boolean visited[]; private int pre[]; private int nodes; public MaxFlow( int[][] capacity, int nodes ) { this.capacity = capacity; this.nodes = nodes; this.flow = new int[nodes][nodes]; this.pre = new int[nodes]; this.visited = new boolean[nodes]; } public int maxFlow( int src, int des ) { int maxFlow = 0; for( int i = 0; i < nodes; i++ ) for( int j = 0; j < nodes; j++ ) flow[i][j] = 0; while( true )//find a augment path { for( int i = 0; i < nodes; i++ ) { visited[i] = false; } pre[src] = -1; if(!BFS( src, des )){// the BFS break; } /*DFS(src,des);//DFS if(!visited[des]) break;*/ int increment = Integer.MAX_VALUE; for( int i = des; pre[i] >= src; i = pre[i] ) { //find the min flow of the path increment = Math.min( increment, capacity[pre[i]][i] - flow[pre[i]][i] ); } //update the flow for( int i = des; pre[i] >= src; i = pre[i] ) { flow[pre[i]][i] += increment; flow[i][pre[i]] -= increment; } //increase the maxFow with the increment maxFlow += increment; } return maxFlow; } private void DFS(int src, int des){ visited[src] = true; for(int i = 0; i < nodes; i++){ if(!visited[i] && ( capacity[src][i] - flow[src][i] > 0) ){ pre[i] = src;//record the augment path visited[i] = true; DFS(i,des); } } } private boolean BFS( int src, int des ) { Queue<Integer> queue = new LinkedList<Integer>(); queue.add( src ); visited[src] = true; while( !queue.isEmpty() ) { int node = queue.poll(); for( int i = 0; i < nodes; i++ ) { if( !visited[i] && (capacity[node][i] - flow[node][i] > 0) ) { queue.add( i ); visited[i] = true; pre[i] = node;//record the augment path } } } return visited[des]; } public static void main( String[] args ) { int nodes, edges; Scanner scanner = new Scanner( System.in ); nodes = scanner.nextInt(); edges = scanner.nextInt(); int[][] capacity = new int[nodes][nodes]; int src, des, c; for( int i = 0; i < edges; i++ ) { src = scanner.nextInt(); des = scanner.nextInt(); c = scanner.nextInt(); capacity[src][des] = c; } MaxFlow maxFlow = new MaxFlow( capacity, nodes ); System.out.println( maxFlow.maxFlow( 0, nodes - 1 ) ); } }
输入:
6 10 // 6 nodes, 10 edges
0 1 16 // capacity from 0 to 1 is 16
0 2 13 // capacity from 0 to 2 is 13
1 2 10 // capacity from 1 to 2 is 10
2 1 4 // capacity from 2 to 1 is 4
3 2 9 // capacity from 3 to 2 is 9
1 3 12 // capacity from 1 to 3 is 12
2 4 14 // capacity from 2 to 4 is 14
4 3 7 // capacity from 4 to 3 is 7
3 5 20 // capacity from 3 to 5 is 20
4 5 4 // capacity from 4 to 5 is 4
输出:
23
评论
6 楼
fuliang
2010-09-17
sulifeng 写道
DFS()那个函数是不是没有调用? 该什么时候调用呢? 难道和BFS()有着完全相同的效果?
这个算法广度和深度优先遍历都是一样的,写了两种
5 楼
sulifeng
2010-09-15
DFS()那个函数是不是没有调用? 该什么时候调用呢? 难道和BFS()有着完全相同的效果?
4 楼
fuliang
2010-08-27
shenwenting520 写道
你这个程序是不有外部数据的输入,我运行了此程序却没有要求输入,也无输出。
是啊,代码下面有输入输出实例:
输入:
6 10 // 6 nodes, 10 edges
0 1 16 // capacity from 0 to 1 is 16
0 2 13 // capacity from 0 to 2 is 13
1 2 10 // capacity from 1 to 2 is 10
2 1 4 // capacity from 2 to 1 is 4
3 2 9 // capacity from 3 to 2 is 9
1 3 12 // capacity from 1 to 3 is 12
2 4 14 // capacity from 2 to 4 is 14
4 3 7 // capacity from 4 to 3 is 7
3 5 20 // capacity from 3 to 5 is 20
4 5 4 // capacity from 4 to 5 is 4
输出:
23
3 楼
shenwenting520
2010-08-27
你这个程序是不有外部数据的输入,我运行了此程序却没有要求输入,也无输出。
2 楼
fuliang
2009-06-27
恩,有点问题,可以改成!=就可以了吧
恩,有点问题,可以改成!=然后再加一个单独处理pre[i]==src的,就可以了吧
microgrape 写道
代码这个地方不太通用啊
maxFlow函数中update the flow的部分
for( int i = des; pre[i] >= src; i = pre[i] )
如果src到des的顶点序号不是递增的 就不对啦
maxFlow函数中update the flow的部分
for( int i = des; pre[i] >= src; i = pre[i] )
如果src到des的顶点序号不是递增的 就不对啦
恩,有点问题,可以改成!=然后再加一个单独处理pre[i]==src的,就可以了吧
1 楼
microgrape
2009-06-27
代码这个地方不太通用啊
maxFlow函数中update the flow的部分
for( int i = des; pre[i] >= src; i = pre[i] )
如果src到des的顶点序号不是递增的 就不对啦
maxFlow函数中update the flow的部分
for( int i = des; pre[i] >= src; i = pre[i] )
如果src到des的顶点序号不是递增的 就不对啦
发表评论
-
二分查找之变型题目
2010-10-24 12:40 2158二分查找算法在各个公司的笔试面试题大量出现,通常不是简单一眼就 ... -
一道笔试题(创新工厂)解法
2010-10-21 17:44 1855一个帖子http://www.iteye.com/topic/ ... -
[zz]大数据量,海量数据 处理方法总结
2010-08-27 22:24 2273大数据量的问题是很多面试笔试中经常出现的问题,比如baidu ... -
Trie and suffix array
2010-04-13 20:54 1927字典数Trie和后缀数组suffix array是处理字符串操 ... -
金币问题
2009-11-09 08:41 2018今年某公司的笔试题: 一个矩阵地图,每一个元素值代表金币数, ... -
楼梯问题
2009-11-09 08:19 1578hl给我的几道某公司的算法题: 1、 有个 100 级的 ... -
一道考察模拟乘法的题目
2009-11-07 22:37 1423今天hl和我讨论一道题目: 写道 整形数组如a={1,4, ... -
链表归并
2009-11-07 21:40 1038以前gx同学问的某某公司的笔试题,写一下练练(纯手写,没编译过 ... -
找出出现次数超过一半的数字
2009-11-07 21:23 1891hl同学问我一道这个题,想了一种方法,感觉还是不错的,只扫描一 ... -
有道难题以超低分晋级
2009-06-10 11:36 1568有道难题比赛居然晋级了,可以领到一个t-shirt。 -
逆序数/逆序数对
2009-06-09 23:17 3785逆序数是个常遇到的问题,主要有两种解法: O(n^2)的方法: ... -
有道难题topcoder
2009-05-31 23:55 2463今天做了有道topcoder的题目,也是第一次在topcode ... -
百度之星第一场题目
2009-05-31 00:03 3655由于不符合参赛条件,未能参加百度之星,看了题目还挺有意思,把题 ... -
一个对字符串很好的Hash函数ELFHHash
2009-05-03 21:41 2282#include<stdio.h> #defin ... -
大数/高精度加减乘除取模[收藏]
2009-04-16 19:38 5070#include <iostream> #i ... -
带重复数字的全排列
2009-04-16 18:58 3896上次gx同学问我一道又重复数字的全排列的问题,我当时用set保 ... -
差分约束系统
2009-04-15 16:00 3749(本文假设读者已经有以下知识:最短路径的基本性质、Bellma ... -
二分图匹配
2009-04-15 15:40 3730二分图最大匹配的匈牙利算法 二分图是这样一个图,它的顶点可以分 ... -
线段树
2009-03-24 10:58 1688把问题简化一下: 在自然数,且所有的数不大于30000的 ... -
树状数组
2009-03-24 10:39 2346树状数组是一种非常优雅的数据结构. 当要频繁的对数 ...
相关推荐
基于Ford-Fulkerson算法的最大流算法,通信网作业
理解并实现最大流问题和FORD-FULKERSON算法,不仅可以帮助我们掌握网络流理论,还有助于提升对图算法和优化问题的解决能力。在这个程序中,通过调整图的结构和观察运行时间,我们可以深入探究算法的实际效果和潜在的...
Ford-Fulkerson算法是解决这类问题的一种有效方法,它通过增广路径来逐步增加网络中的流量,直到达到最大流。 **最大流问题**:在一个有向图中,每条边都有一个容量限制,从源点到汇点的流量不能超过这些限制。最大...
Ford-Fulkerson算法是求解网络最大流的一种基础且重要的方法,由L.R. Ford和D.R. Fulkerson于1956年提出。下面将详细介绍该算法以及其C++实现的关键点。 ### Ford-Fulkerson算法的基本思想 1. **增广路径**:在...
Ford-Fulkerson方法是一种在图论中用于求解网络流问题中最大流问题的算法。该算法由L. R. Ford, Jr. 和 D. R. Fulkerson 在1962年提出,因此得名。最大流问题是指在一个网络中,找到从源点到汇点的最大可能流量,...
网络最大流_Ford-Fulkerson 算法 网络最大流问题是计算机科学和运筹学中一个经典的问题,它是指在给定的网络中,寻找从源点到汇点的最大流。Ford-Fulkerson 算法是一种常用的解决网络最大流问题的算法。 Ford-...
使用Ford-Fulkerson算法解决最大流问题 Ford-Fulkerson算法是一种常用的最大流算法,它可以解决网络流问题的最大流问题。该算法的基本思想是从某个可行流F出发,找到关于这个流的一个可改进路径P,然后沿着P调整F,...
本资源是使用FF算法计算网络最大流的算法,内容全网非常简洁易懂,代码注释十分全面。
总结来说,Ford-Fulkerson算法是一种有效的解决最大流问题的方法,它通过不断寻找和增加增广路径来逐步接近最大流。在实际应用中,如运输、电路设计、资源分配等领域,该算法有着广泛的应用。尽管该算法可能存在效率...
福特-富尔克森(Ford-Fulkerson)算法是一种经典的图论算法,用于解决网络最大流问题。在计算机科学和图论中,网络最大流问题是一个寻找从源节点到汇节点的最大流量的问题,其中网络表示为带权重的有向图,边上的...
0851_极智开发_解读Ford-Fulkerson算法及示例代码
最大流问题的 Ford-Fulkerson 算法的python实现。包括图形读取、残差图计算、路径查找以及使用 NetworkX 和 Matplotlib 进行可视化。非常适合学习网络流算法.zip
首先,Ford-Fulkerson算法是一种用于求解最大流问题的图理论算法。最大流问题是在给定的有向图中寻找一个源节点到汇点的最大流量,该问题在资源分配、网络设计等领域有着广泛的应用。该算法的核心思想是增广路径,即...
福特-富克森(Ford-Fulkerson)算法是一种在图论中用于寻找网络最大流的算法,它由L.L. Ford和D.R. Fulkerson于1956年提出。在网络流问题中,我们有一个带容量限制的有向图,其中每条边都有一个非负的容量值,目标是...
Ford-Fulkerson算法演示文稿,展示了这个算法的整个操作流程!
福特-富克森(Ford-Fulkerson)算法是图论中的一个重要算法,主要用于求解网络流问题,特别是在最大流问题中的应用。这个算法基于增广路径的概念,通过寻找从源点到汇点的未饱和边来逐步增加网络的流量,直到无法再...
福特富尔克森算法Fork Fulkerson 算法的实现。入门 meteor add ccorcos:ford-fulkerson应用程序接口您应该只查看源代码。 初始化图形。 Graph = FordFulkerson()添加带有Graph.added source, sink, capacity, ...