Network Flow

The Maximum Network Flow Problem Let’s begin with some key ideas about the network flow problem and relevant concepts. Given a directed graph $G=(V,E)$, a source node $s \in V$, and a sink node $t \in V$. For each $e \in E$, there is a capacity, denoted as $c(e)$ or $c(u,v)$. When $(u,v) \notin E $, we assume $c(u,v)=0$. Our goal for the maximum flow problem is to push as much flow as possible from $s$ to $t$ in the graph (network). The rules are that no edge can have flow exceeding its capacity, and for any vertex except $s$ and $t$, the in to the vertex must equal the flow out from the vertex. That is, ...