LABELING ALGORITHM

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

The Ford-Fulkerson max flow labeling algorithm (c = capacity).

Input. source (s), destination (t), capacities (c).

Output. max flow from s to t.

• Initialize all flows to be zero and assign the label (-,inf) to the source. All other nodes are unlabeled, and all nodes (including the source) are unscanned.
• Labeling process: Select any labeled, unscanned node, say k with label (a,b). If node j is an unlabeled neighbor and x(k, j) < c(k, j), assign the label (k+,b*) to node j, where b* = Min(b, c(k,j)-x(k,j)). If node j is an unlabeled neighbor and x(j, k) > 0, assign the label (k-,b*) to node j, where b* = Min(b, x(j,k)). (In either case, define node j as labeled, but unscanned, while node 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 (t) have label (a,b). If a is k+, replace x(k,t) by x(k,t)+b; if it is (k-,b), replace x(k,t) by x(k,t)-b. In either case, apply the flow change (b or -b) along the path back to the source. The result is a new flow that is b more than it was. Erase labels, except on the source, and go to the labeling process. (See technical note , with an example.)

Dijkstra's shortest path algorithm (c = distance).

Input. source (s), destinations (T not Ø), distances (c).

Output. shortest path from s to each node in T.

• Initialize labels: L(v)=inf for v not= s and L(s)=0. Set S=Ø.
• Label: select u in argmin(L(v): v in V\S) (terminate if S=V). Then, update S := S\/(u), and for v in V\S: if L(u) + c(u,v) < L(v), set L(v) := L(u) + c(u,v).

Terminate when T is a subset of S (i.e., all destination nodes are labeled with their shortest distance from node s).

A generic shortest path labeling algorithm from all nodes to destination node t (c = distance).

Input. destination (t), distances (c).

Output. shortest path from each node to t.

• Initialize labels, L(v) = estimate of shortest path length from node v to node t, with L(t) = 0.
• Label: Find an arc, say (i, j), that violates the distance equations, say L(j) > L(i) + c(i, j). If none, terminate; otherwise, update the label:L(j) = L(i) + c(i, j).

The labeling step is repeated until there are no violations. At termination, L(j) = length of shortest path from node j to node t.

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