than and at the beginning, it is preferable to perform a backward breadth-first search from to compute exact labels. The algorithm is typically separated into two phases. Phase one computes a maximum pre-flow by discharging only active nodes whose labels are below . Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach to . It can be shown that phase two has time complexity regardless of the order of push and relabel operations and is therefore dominated by phase one. Alternatively, it can be implemented using flow decomposition. Heuristics are crucial to improving the empirical performance of the algorithm. Two commonly used heuristics are the gap heuristic and the global relabeling heuristic. The gap heuristic detects gaps in the labeling function. If there is a label for which there is no node such that , then any node with has been disconnected from and can be relabeled to immediately. The global relabeling heuristic periodically performs backward breadth-first search from in to compute the exact labels of the nodes. Both heuristics skip unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees. Sample implementations #include <stdlib.h> #include <stdio.h> #define NODES 6 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define INFINITE 10000000 void push(const int * const * C, int ** F, int *excess, int u, int v) { int send = MIN(excess[u], C[u][v] - F[u][v]); F[u][v] += send; F[v][u] -= send; excess[u] -= send; excess[v] += send; } void relabel(const int * const * C, const int * const * F, int *height, int u) { int v; int min_height = INFINITE; for (v = 0; v < NODES; v++) { if (C[u][v] - F[u][v] > 0) { min_height = MIN(min_height, height[v]); height[u] = min_height + 1; } } }; void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) { while (excess[u] > 0) { if (seen[u] < NODES) { int v = seen[u]; if ((C[u][v] - F[u][v] > 0) && (height[u] > height[v])) { push(C, F, excess, u, v); } else { seen[u] += 1; } } else { relabel(C, F, height, u); seen[u] = 0; } } } void moveToFront(int i, int *A) { int temp = A[i]; int n; for (n = i; n > 0; n--) { A[n] = A[n-1];