Let's apply the Labeling Algorithm to the network flow shown in Figure 13.2. Then we start with the source: \begin{equation*} S:\quad(*,+,\infty) \end{equation*} Since the source $S$ is the first vertex labeled, it is also the first one scanned. So we look at the neighbors of $S$ using the pseudo-alphabetic order on the vertices. Thus, the first one to be considered is vertex $B$ and since the edge $(S,B)$ is not full, we label $B$ as \begin{equation*} B:\quad(S,+,8). \end{equation*} We then consider vertex $E$ and label it as \begin{equation*} E:\quad(S,+,28). \end{equation*} Next is vertex $F$, which is labeled as \begin{equation*} F:\quad(S,+,15). \end{equation*} At this point, the scan from $S$ is complete.

The first vertex after $S$ to be labeled was $B$, so we now scan from $B$. The (unlabeled) neighbors of $B$ to be considered, in order, are $A$, $C$, and $D$. This results in the following labels: \begin{align*} A\amp:\quad(B,+,8)\\ C\amp:\quad(B,+,8)\\ D\amp:\quad(B,-,6) \end{align*} The next vertex to be scanned is $E$, but $E$ has no unlabeled neighbors, so we then move on to $F$, which again has no unlabeled neighbors. Finally, we scan from $A$, and using the pseudo-alphabetic order, we first consider the sink $T$ (which in this case is the only remaining unlabeled vertex). This results in the following label for $T$. \begin{equation*} T:\quad(A,+,8) \end{equation*} Now that the sink is labeled, we know there is an augmenting path. We discover this path by backtracking. The sink $T$ got its label from $A$, $A$ got its label from $B$, and $B$ got its label from $S$. Therefore, the augmenting path is $P=(S,B,A,T)$ with $\delta=8$. All edges on this path are forward. The flow is then updated by increasing the flow on the edges of $P$ by $8$. This results in the flow shown in Figure 13.12. The value of this flow is $38$.

Here is the sequence (reading down the columns) of labels that will be found when the labeling algorithm is applied to this updated flow. (Note that in the scan from $S$, the vertex $B$ will not be labeled, since now the edge $(S,B)$ is full.) \begin{align*} S:\amp\quad(*,+,\infty)\amp D:\amp\quad(E,+,12)\\ E:\amp\quad(S,+,28)\amp A:\amp\quad(F,+,12)\\ F:\amp\quad(S,+,15)\amp C:\amp\quad(B,+,10)\\ B:\amp\quad(E,+,19)\amp T:\amp\quad(A,+,12) \end{align*} This labeling results in the augmenting path $P=(S,F,A,T)$ with $\delta=12$.

After this update, the value of the flow has been increased and is now $50=38+12$. We start the labeling process over again and repeat until we reach a stage where some vertices (including the source) are labeled and some vertices (including the sink) are unlabeled.

# Subsection13.5.1How the Labeling Algorithm Halts

Consider the network flow in Figure 13.13.

The value of the current flow is $172$. Applying the labeling algorithm using the pseudo-alphabetic order results in the following labels (reading down the columns): \begin{align*} S:\amp\quad(*,+,\infty)\amp E:\amp\quad(I,-,3)\\ C:\amp\quad(S,+,8)\amp G:\amp\quad(E,-,3)\\ F:\amp\quad(S,+,23)\amp L:\amp\quad(E,+,3)\\ H:\amp\quad(C,+,7)\amp B:\amp\quad(G,+,3)\\ I:\amp\quad(H,+,7)\amp T:\amp\quad(L,+,3) \end{align*} These labels result in the augmenting path $P=(S,C,H,I,E,L,T)$ with $\delta =3$. After updating the flow and increasing its value to $175$, the labeling algorithm halts with the following labels: \begin{align*} S:\amp\quad(*,+,\infty)\amp H:\amp\quad(C,+,4)\\ C:\amp\quad(S,+,5)\amp I:\amp\quad(H,+,4)\\ F:\amp\quad(S,+,23) \end{align*} Now we observe that the labeled and unlabeled vertices are $L=\{S,C,F,H,I\}$ and $U=\{T,A,B,D,E,G,J,K\}$. Furthermore, the capacity of the cut $V=L\cup U$ is \begin{equation*} 41+8+23+8+13+29+28+25 = 175. \end{equation*} This shows that we have found a cut whose capacity is exactly equal to the value of the current flow. In turn, this shows that the flow is optimal.