compute optimal value for max flow problem
MaxFlow(G, s, t)
vertex of the graph (source)
vertex of the graph (sink)
The MaxFlow command returns the optimal value for the max flow problem along with an optimal flow (as a Matrix).
The algorithm used is the Push-Relabel (Push-Preflow) algorithm of Goldberg et al. (see Introduction to Algorithms, Cormen, Leiserson, Rivest, 2nd edition). The complexity is O⁡n2⁢m where n=|V| is the number of vertices of G and m=|E| is the number of edges.
A ≔ Matrix⁡0,1,0,4,0,0,0,0,1,0,3,0,0,1,0,0,0,1,0,0,3,0,1,0,0,0,0,1,0,4,0,0,0,0,0,0
N ≔ Digraph⁡A,weighted
N≔Graph 1: a directed weighted graph with 6 vertices and 10 arc(s)
Download Help Document