One of the mathematical necessary conditions for maximization, used routinely in solving economic models. Typically, it consists of setting equal to zero the derivative of the function being maximized (or its Lagrangian) with respect to a variable that can be controlled.
first-order conditions The conditions for a function to take a stationary value. If y = f (x), the first-order condition for a stationary value is dy/dx = fx = 0.
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.
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 VS} (terminate if S=V). Then, update S := S/{u}, and for v in VS: 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.
Suppose x* is in argmax{f(x): g(x) <= 0, h(x) = 0}, where f, g, h are in C^1. Then, there exist multipliers (u, v) for which the following conditions hold: