Labeling algorithm

From Glossary

Jump to: navigation, search


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.


Views
Personal tools