 # Labeling algorithm

A class of algorithms for path-related problems on graphs and networks. To illustrate, consider a network $LaTeX: [V,A]$ with arc values $LaTeX: c$.

• The Ford-Fulkerson max flow labeling algorithm ( $LaTeX: c$ is capacity).
• Input is source $LaTeX: (s)$, destination $LaTeX: (t)$, and capacities $LaTeX: (c)$. Output is the max flow from $LaTeX: s$ to $LaTeX: t$.
• Initialize all flows to be zero and assign the label $LaTeX: (-,\infty)$ to the source. All other nodes are unlabeled, and all nodes (including the source) are unscanned.
• Labeling process: Select any labeled, unscanned node, say $LaTeX: k$ with label $LaTeX: (a,b)$. If node $LaTeX: j$ is an unlabeled neighbor and $LaTeX: x_{kj} < c_{kj}$, assign the label $LaTeX: (k+,b^*)$ to node $LaTeX: j$, where $LaTeX: b^* = \min \{b, c_{kj}-x_{kj}\}$. If node $LaTeX: j$ is an unlabeled neighbor and $LaTeX: x_{jk} > 0$, assign the label $LaTeX: (k-,b^*)$ to node $LaTeX: j$, where $LaTeX: b* = \min\{b, x_{jk}\}$. (In either case, define node $LaTeX: j$ as labeled, but unscanned, while node $LaTeX: k$ is now labeled and scanned.) Repeat this until either the sink is labeled and unscanned, or until no more labels can be assigned. In the latter case terminate; in the former case, go to the flow change step.
• Flow change: Let the sink $LaTeX: (t)$ have label $LaTeX: (a,b)$. If $LaTeX: a$ is $LaTeX: k+$, replace $LaTeX: x_{kt}$ by $LaTeX: x_{kt}+b$; if it is $LaTeX: (k-,b)$, replace $LaTeX: x_{kt}$ by $LaTeX: x_[kt}-b$. In either case, apply the flow change ( $LaTeX: b$ or $LaTeX: -b$) along the path back to the source. The result is a new flow that is $LaTeX: b$ more than it was. Erase labels, except on the source, and go to the labeling process.
• Dijkstra's shortest path algorithm ( $LaTeX: c$ is distance).
• Input is source $LaTeX: (s)$, destinations $LaTeX: (T \neq \emptyset)$, and distances $LaTeX: (c)$. Output is a shortest path from $LaTeX: s$ to each node in $LaTeX: T$.
• Initialize labels: $LaTeX: L_v = \infty$ for $LaTeX: v \neq s$ and $LaTeX: L_s=0$. Set $LaTeX: S=\emptyset$.
• Label: select $LaTeX: u \in \arg\min {L_v: v \in V\backslash S\}$ (terminate if $LaTeX: S=V$). Then, update $LaTeX: S := S \cup \{u\}$, and for $LaTeX: v \in V\backslash S$: if $LaTeX: L_u + c_{uv} < L_v$, set $LaTeX: L_v := L_u + c_{uv}.$
• Terminate when $LaTeX: T$ is a subset of $LaTeX: S$ (i.e., all destination nodes are labeled with their shortest distance from node $LaTeX: s$).
• A generic shortest path labeling algorithm from all nodes to destination node $LaTeX: t$ ( $LaTeX: c$ is distance).
• Input is destination $LaTeX: (t)$ and distances $LaTeX: (c$). Output is a shortest path from each node to $LaTeX: t$.
• Initialize labels, $LaTeX: L_v$ is the estimate of a shortest path length from node $LaTeX: v$ to node $LaTeX: t$, with $LaTeX: L_t = 0.$
• Label: Find an arc, say $LaTeX: (i, j)$, that violates the distance equations, say $LaTeX: L_j > L_i + c_{ij}$. If none, terminate; otherwise, update the label: $LaTeX: L_j = L_i + c_{ij}$.
• The labeling step is repeated until there are no violations. At termination, $LaTeX: L_j$ is the length of a shortest path from node $LaTeX: j$ to node $LaTeX: t$.

Another type of labeling algorithm occurs in simplicial subdivision, used to compute a fixed point that represents an economic equilibrium.