# Labeling algorithm

### From Glossary

A class of algorithms for path-related problems on graphs and networks. To illustrate,
consider a network with arc values .

- The Ford-Fulkerson max flow labeling algorithm ( is capacity).
- Input is source , destination , and capacities . Output is the max flow from to .
- Initialize all flows to be zero and assign the label to the source. All other nodes are unlabeled, and all nodes (including the source) are unscanned.
- Labeling process: Select any labeled, unscanned node, say with label . If node is an unlabeled neighbor and , assign the label to node , where . If node is an unlabeled neighbor and , assign the label to node , where . (In either case, define node as labeled, but unscanned, while node 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 have label . If is , replace by ; if it is , replace by . In either case, apply the flow change ( or ) along the path back to the source. The result is a new flow that is more than it was. Erase labels, except on the source, and go to the labeling process.

- Dijkstra's shortest path algorithm ( is distance).
- Input is source , destinations , and distances . Output is a shortest path from to each node in .
- Initialize labels: for and . Set .
- Label: select (terminate if ). Then, update , and for : if , set
- Terminate when is a subset of (i.e., all destination nodes are labeled with their shortest distance from node ).

- A generic shortest path labeling algorithm from all nodes to destination node
( is distance).
- Input is destination and distances ). Output is a shortest path from each node to .
- Initialize labels, is the estimate of a shortest path length from node to node , with
- Label: Find an arc, say , that violates the distance equations, say . If none, terminate; otherwise, update the label: .

The labeling step is repeated until there are no violations. At termination, is the length of a shortest path from node to node .

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