I've been struggling with the notion of paths in residual graphs for $2$ days now, but I can't seem to find a reasonable enough explanation. I've checked out this post and countless others like it, but all of them seem to be lacking convincing justification.
Some context for my conundrum :
While trying to find max flows in a greedy manner that only traverses the given network, one might encounter a blocking flow that prevents us from exploring other paths:
As an example, consider trying to increase the flow after initially taking the path $X - B - C - Y$. We manage to push $1$ unit of flow through this path. At the next iteration, we manage to find $X - A - C - Y$ and push another unit of flow and halt at a suboptimal solution.
The best solution could have been found by traversing the graph differently, as follows in the next picture :
Since we can't actually predict the optimal sequence of paths, the concept of residual network is introduced. However, I haven't been able to find on the web or by myself an explanation of why does traversing paths on residual networks actually produce the optimal solution.
Upon traversing the path given in the first figure, 'Figure 2a' the following residual network is produced :
Now we're not stuck anymore, and can use the back edge $C - B$ to increase the flow. No explanation as to why this is correct is given. As per my understanding, back edges are introduced so that we may go backwards to edges that may be used to increase the flow.
However, I fail to understand why do we incrementally take the flow we pushed say on back edges and add it back to the front edges when we traverse a path that contains back edges. To visualize this, refer to the next figure, which simply illustrates the state of the residual network after walking the augmenting path through the back edge $C - B$ :
Asides from that, I can't understand the bijection between using the residual networks and only traversing the initial graph in the 'right' way.
Namely, how does the optimal sequence of traversals on the initial network correspond with the paths we actually take on the residual graphs?
I've seen quite a few Quora and cs.stack.exchange posts that simply 'explain' the residual graph as either 'pushing back flow', or 'canceling flow' which make no actual sense to me when performing the algorithm by hand, so I'm at a loss here.
First, let's think of the flow not in terms of its global structure (the sum of weighted paths from $X$ to $Y$) but in terms of its local structure (an assignment of values to each edge such that the total in-flow equals the total out-flow at each vertex except $X$ and $Y$).
Of course, in both interpretations, there's still the capacities on the edges to consider.
Given two different flows, define their difference to be the assignment of values to edges that assigns to each edge the difference between the first flow at that edge and the second flow. Why do we care about this difference to begin with? Because if we want to go from the flow in Figure 2a to the flow in Figure 1a, that corresponds to adding a "flow difference" to each edge, so we want to know what the flow difference can look like.
A flow difference is a lot like a flow: it assigns values to each edge such that the total in-flow equals the total out-flow at each vertex except $X$ and $Y$. However, it does not respect the capacities of the original graph. For example, the flow difference between Figure 2a and Figure 1a assigns a value of $-1$ to the edge $B \to C$.
If we are currently at the flow in Figure 2a, we can write down the range of possible values that a flow difference between the current flow and another valid flow can have. For example, the current flow at edge $C \to Y$ is $1$; another valid flow can have any value in $[0,2]$ at that edge; so the flow difference can be any value in the range $[-1,1]$.
If we label each edge with the range of possible values a flow difference from Figure 2a can have on it, we get something that looks a lot like the residual graph:
The only difference is that where this graph has a single edge with label $[-1,4]$, the residual graph has a forward edge with label $4$ and a backward edge with label $1$. So let's explain that difference.
In a flow difference, we can satisfy the local flow condition on vertices by something that doesn't look like a path (or even a sum of paths). For example, assigning the value $1$ to the edge $A \to C$ and the value $-1$ to the edge $B \to C$ satisfies the local flow condition at vertex $C$.
However, if we take any undirected path in this network and give each edge along the path the value $1$ if taken forward and $-1$ if taken backward, then that will always satisfy the local flow condition. For example, if we have edges $u \to v$ and $v \gets w$ along the path, then we assign $1$ to the first edge and $-1$ to the second edge, so the total in-flow at $v$ is $1 + (-1)=0$, satisfying the local condition at $v$.
More generally, the valid flow differences are precisely the weighted sums of such undirected paths whose values at each edge are in the range given by the figure above. So if we find any such path, that's a valid flow difference, and we can add some multiple of it to the flow in Figure 2a to improve it. In particular, to get from Figure 2a to Figure 1a, we add the flow difference given by the undirected path $X \to A \to C \gets B \to D \to E \to Y$.
Thinking about undirected paths is weird. But we notice that if an edge has label $[-a,b]$, that means it can have flow at most $b$ when taken forward, and at most $a$ when taken backward. This is exactly the same behavior that we'd get if we had an edge with label $[0,b]$ and an edge in the reverse direction and label $[0,a]$ - except then, we wouldn't need to take any backward edges.
(For example, if we take a fictional edge $C \to B$ with value $1$, that corresponds to taking the edge $B \to C$ with value $-1$: but now it lets us think about the directed path $X \to A \to C \to B \to D \to E \to Y$ rather than the undirected path we had earlier.)
So that's how we get the residual graph: it's simply the graph in the figure above, but each edge that has a negative lower bound on the capacity is replaced by two edges, one in each direction, that have the same effect.