APPENDIX
DINIC’S ALGORITHM FOR MAXIMUM FLOW IN
A NETWORK
In this section, we describe Dininc’s algorithm for maximum flow on a net-
work. The following are some additional concepts used in the description of
the algorithm.
Blocking Flow
A flow on a network is a blocking flow if every path from source to sink
contains a saturated edge (edge with full capacity flow through it). An ex-
ample of a blocking flow is shown in Figure 10.4. Also note that the flow is
not maximum. The optimal flow is shown in Figure 10.4.
Residual Graph
Associated with every feasible flow through the network is a weighted di-
graph called the residual graph. This is constructed in the following manner.
LetCbe the capacity of the edge connecting vertices AandB. Let Fbe the
flow from AtoB. The residual graph has a directed edge from AtoBwith
capacityC–Fand another from BtoAwith capacity F. All edges with zero
capacity are removed from the graph thus constructed. The resultant graph
is the residual graph. An example of the residual graph corresponding to the
problem and the blocking flow is shown in Figure 10.4.
Flow Augmenting Paths
A flow augmenting path is a path on the residual graph from source to sink.
The maximum flow that can be sent through this path is limited by capacity
of the edges in the path. It is equal to the smallest capacity of an edge along
the path.
Dinic’s Algorithm
The steps in Dinic’s Algorithm are as follows:
- Find a blocking flow for a given network.
- Construct the residual graph corresponding to the current flow.
- Find the shortest length augmenting path on the residual graph. (The
length of the path is equal to the number of edges in it.) If such a path
does not exist, then the current flow is the maximum flow. - If such a path exists, then augment the flow along the path. (Make the
corrections to the flow graph and the residual graph.) Go to Step 3.
168 RISK ARBITRAGE PAIRS