`

最大流Ford-Fulkerson算法

阅读更多
算法导论对最大流算法有很详细的介绍,今天实现了最大流Ford-Fulkerson的算法,包括BFS和DFS来搜索增广路径。
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
1
0
分享到:
评论
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  
恩,有点问题,可以改成!=就可以了吧
microgrape 写道
代码这个地方不太通用啊
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的顶点序号不是递增的 就不对啦

相关推荐

    基于Ford-Fulkerson算法的matlab最大流算法

    基于Ford-Fulkerson算法的最大流算法,通信网作业

    最大流 FORD-FULKERSON算法

    理解并实现最大流问题和FORD-FULKERSON算法,不仅可以帮助我们掌握网络流理论,还有助于提升对图算法和优化问题的解决能力。在这个程序中,通过调整图的结构和观察运行时间,我们可以深入探究算法的实际效果和潜在的...

    最大流/最小割Ford-Fulkerson算法的代码实现

    Ford-Fulkerson算法是解决这类问题的一种有效方法,它通过增广路径来逐步增加网络中的流量,直到达到最大流。 **最大流问题**:在一个有向图中,每条边都有一个容量限制,从源点到汇点的流量不能超过这些限制。最大...

    最大流Ford-Fulkerson算法源代码

    Ford-Fulkerson算法是求解网络最大流的一种基础且重要的方法,由L.R. Ford和D.R. Fulkerson于1956年提出。下面将详细介绍该算法以及其C++实现的关键点。 ### Ford-Fulkerson算法的基本思想 1. **增广路径**:在...

    Ford-Fulkerson方法.pdf

    Ford-Fulkerson方法是一种在图论中用于求解网络流问题中最大流问题的算法。该算法由L. R. Ford, Jr. 和 D. R. Fulkerson 在1962年提出,因此得名。最大流问题是指在一个网络中,找到从源点到汇点的最大可能流量,...

    网络最大流_Ford-Fulkerson算法.docx

    网络最大流_Ford-Fulkerson 算法 网络最大流问题是计算机科学和运筹学中一个经典的问题,它是指在给定的网络中,寻找从源点到汇点的最大流。Ford-Fulkerson 算法是一种常用的解决网络最大流问题的算法。 Ford-...

    使用标号算法(Ford-Fulkerson)解决最大流问题

    使用Ford-Fulkerson算法解决最大流问题 Ford-Fulkerson算法是一种常用的最大流算法,它可以解决网络流问题的最大流问题。该算法的基本思想是从某个可行流F出发,找到关于这个流的一个可改进路径P,然后沿着P调整F,...

    C++语言Ford-Fulkerson算法(含大量注释)

    本资源是使用FF算法计算网络最大流的算法,内容全网非常简洁易懂,代码注释十分全面。

    Ford-Fulkerson算法演示

    总结来说,Ford-Fulkerson算法是一种有效的解决最大流问题的方法,它通过不断寻找和增加增广路径来逐步接近最大流。在实际应用中,如运输、电路设计、资源分配等领域,该算法有着广泛的应用。尽管该算法可能存在效率...

    ford-fulkerson算法求网络最大流(java实现)

    福特-富尔克森(Ford-Fulkerson)算法是一种经典的图论算法,用于解决网络最大流问题。在计算机科学和图论中,网络最大流问题是一个寻找从源节点到汇节点的最大流量的问题,其中网络表示为带权重的有向图,边上的...

    0851-极智开发-解读Ford-Fulkerson算法及示例代码

    0851_极智开发_解读Ford-Fulkerson算法及示例代码

    最大流问题的 Ford-Fulkerson 算法的python实现

    最大流问题的 Ford-Fulkerson 算法的python实现。包括图形读取、残差图计算、路径查找以及使用 NetworkX 和 Matplotlib 进行可视化。非常适合学习网络流算法.zip

    bellman_Ford.rar_Ford-Fulkerson_bellman_cspf_ford_部署优化算法

    首先,Ford-Fulkerson算法是一种用于求解最大流问题的图理论算法。最大流问题是在给定的有向图中寻找一个源节点到汇点的最大流量,该问题在资源分配、网络设计等领域有着广泛的应用。该算法的核心思想是增广路径,即...

    ford_fulkerson算法c程序

    福特-富克森(Ford-Fulkerson)算法是一种在图论中用于寻找网络最大流的算法,它由L.L. Ford和D.R. Fulkerson于1956年提出。在网络流问题中,我们有一个带容量限制的有向图,其中每条边都有一个非负的容量值,目标是...

    Ford-Fulkerson演示文稿

    Ford-Fulkerson算法演示文稿,展示了这个算法的整个操作流程!

    毕业设计MATLAB_Ford-Fulkerson算法.zip

    福特-富克森(Ford-Fulkerson)算法是图论中的一个重要算法,主要用于求解网络流问题,特别是在最大流问题中的应用。这个算法基于增广路径的概念,通过寻找从源点到汇点的未饱和边来逐步增加网络的流量,直到无法再...

    meteor-ford-fulkerson:Ford-Fulkerson 最大流最小割算法的简单实现

    福特富尔克森算法Fork Fulkerson 算法的实现。入门 meteor add ccorcos:ford-fulkerson应用程序接口您应该只查看源代码。 初始化图形。 Graph = FordFulkerson()添加带有Graph.added source, sink, capacity, ...

Global site tag (gtag.js) - Google Analytics