University:
Amherst College
Course:
COSC 311 | Algorithms
Academic year:

2022
Views:

187

Pages:

1
Author:

Esther Schaefer

Network Flow: Ford-Fulkerson Algorithm FordFulkerson(G=(V,E), s in V, t in V) set f(u,v) = 0 for all edges (u,v) in E (initial flow is 0) set G_f = G (initially, residual graph is G) while there’s an s-t path in G_f set P = an s-t path in G_f set f’ = augment(f,P) set f = f’ set G_f = G_f’ (update residual graph based on new flow) return f augment(f,P) (f: a flow in G, P: an augmenting path in G_f) set b = minimum edge capacity in P for each edge (u,v) in P if (u,v) is a forward edge in G, set f(u,v) = f(u,v) + b (send more flow) else in G, set f(v,u) = f(v,u) - b (push some flow back) return f (the updated flow)

Network Flow Ford-Fulkerson Algorithm

Related Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock