算法实现/图/最大流/埃德蒙兹-卡普

Java

/*
   * Java Implementation of Edmonds-Karp Algorithm *
   * By: Pedro Contipelli                          *

 Input Format:                                     (Sample Input)

 N , E         | (N total nodes , E total edges) |  4 5
 u1 , v1 , c1  |                                 |  0 1 1000
 u2 , v2 , c2  | Each line u , v , c represents  |  1 2 1
 u3 , v3 , c3  | an edge in the graph from node  |  0 2 1000
  ...          | u to node v with capacity C     |  1 3 1000
 uE , vE , cE  |                                 |  2 3 1000
 
 Nodes 0 and N-1 are assumed to be the source and sink (respectively).
*/

import java.util.*;
public class EdmondsKarp {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);

int nodes = scan.nextInt();
int edges = scan.nextInt();
int source = 0;
int sink = nodes - 1;

Node[] graph = new Node[nodes];

// Initialize each node
for (int i = 0; i < nodes; i++)
	graph[i] = new Node();

// Initialize each edge
for (int i = 0; i < edges; i++) {
	int u = scan.nextInt();
	int v = scan.nextInt();
	int c = scan.nextInt();
	
	// Note edge "b" is not actually in the input graph
	// It is a construct that allows us to solve the problem
	Edge a = new Edge(u , v , 0 , c);
	Edge b = new Edge(v , u , 0 , 0);
	
	// Set pointer from each edge "a" to
	// its reverse edge "b" and vice versa
	a.setReverse(b);
	b.setReverse(a);
	
	graph[u].edges.add(a);
	graph[v].edges.add(b);
}

int maxFlow = 0;

while (true) {
	// Parent array used for storing path
	// (parent[i] stores edge used to get to node i)
	Edge[] parent = new Edge[nodes];
	
	ArrayList<Node> q = new ArrayList<>();
	q.add(graph[source]);
	
	// BFS finding shortest augmenting path
	while (!q.isEmpty()) {
		Node curr = q.remove(0);
		
		// Checks that edge has not yet been visited, and it doesn't
		// point to the source, and it is possible to send flow through it. 
		for (Edge e : curr.edges)
			if (parent[e.v] == null && e.v != source && e.capacity > e.flow) {
				parent[e.v] = e;
				q.add(graph[e.v]);
			}
	}
		
	// If sink was NOT reached, no augmenting path was found.
	// Algorithm terminates and prints out max flow.
	if (parent[sink] == null)
		break;
	
	// If sink WAS reached, we will push more flow through the path
	int pushFlow = Integer.MAX_VALUE;
	
	// Finds maximum flow that can be pushed through given path
	// by finding the minimum residual flow of every edge in the path
	for (Edge e = parent[sink]; e != null; e = parent[e.u])
		pushFlow = Math.min(pushFlow , e.capacity - e.flow);
	
	// Adds to flow values and subtracts from reverse flow values in path
	for (Edge e = parent[sink]; e != null; e = parent[e.u]) {
		e.flow += pushFlow;
		e.reverse.flow -= pushFlow;
	}
	
	maxFlow += pushFlow;
}

System.out.println("Max Flow: " + maxFlow);

scan.close();
}
}

// No explicit constructor is necessary :P

class Node {

// List of edges also includes reverse edges that
// are not in original given graph (for push-back flow)
ArrayList<Edge> edges = new ArrayList<>();

}

class Edge {
	
int u , v , flow , capacity;
Edge reverse;

public Edge(int u , int v , int flow , int capacity) {
	this.u = u;
	this.v = v;
	this.flow = flow;
	this.capacity = capacity;
}

public void setReverse(Edge e) {
	reverse = e;
}

}

MATLAB

此代码是维基百科埃德蒙兹-卡普算法文章中显示的伪代码在 MATLAB 语言中的直接转录。

function [f,F]=EdmondsKarp(C,E,s,t)

%Initial flow is 0
f=0;

imax=size(C,1);
F=zeros(imax);

while(1)
    [m,P]=BreadthFirstSearch(C,E,s,t,F);
    
    %The end is reached when the capacity of the returned path is 0
    if(m==0)
        break;
    end
    
    %The total flow is increased by m
    f=f+m;
    
    %The flow for every edge on the path is increased by m
    v=t;
    while(v~=s)
        u=P(v);
        F(u,v)=F(u,v)+m;
        F(v,u)=F(v,u)-m;
        v=u;
    end
end

end

function [M,P]=BreadthFirstSearch(C,E,s,t,F)

n=size(C,1);
P=zeros(n,1);
M=zeros(n);
M(s)=Inf;

for u=1:n
    P(u)=-1;
end
P(s)=-2;

%Q is used as a queue
Q=[];
Q=vertcat(Q,s);

while(isempty(Q)==0)
    u=Q(1);
    Q(1)='';
    
    neighbors=E{u};
    for i=1:length(neighbors)
        v=neighbors(i);
        if(C(u,v)-F(u,v)>0 && P(v)==-1)
            P(v)=u;
            M(v)=min(M(u),C(u,v)-F(u,v));
            if(v~=t)
                Q(length(Q)+1)=v;
            else
                M=M(t);
                return;
            end
        end
    end
end

M=0;

end