Motivation: In standard augmenting path maxflow algorithms, the inner loop requires finding paths from source to sink in a directed, weighted graph.  Theoretically, it is well-known that in order for the algorithm to even terminate when there are irrational edge capacities, we need to put restrictions on the paths that we find.  The Edmonds-Karp algorithm, for example, tells us to find shortest paths.Empirically, it has been observed that we might also want to find fat (is there a better term for this?) paths.  For example, when using capacity scaling, we find shortest paths that can bear at least $\epsilon$ amount of flow.  There is no restriction on how long the path can be.  When we can no longer find any paths, we decrease $\epsilon$ and repeat.I am interested in optimizing the choice of augmenting paths for a very specific application of max-flow, and I want to explore this tradeoff between short and fat paths.  (Note: it is not necessary for me to always solve the problem.  I am most interested in finding the largest lower bound on flow in the shortest amount of wall time.)Question: Is there a standard way to  interpolate between the shortest path  approach and the capacity-scaling  approach?  That is, is there an  algorithm for finding paths that are  both short and fat, where ideally some  parameter would control how much  length in the path we are willing to  trade off for fatness?  At the extremes, I'd like to be able to recover  shortest paths on one end and capacity scaling-style paths on the other.
Finding short and fat paths
ds.algorithms;graph theory;graph algorithms
In the spirit of your comment about pretty good but not necessarily optimal, I present the following idea with absolutely no guarantee of optimality!For completeness, here is the pseudocode that you referred to (Remark: the algorithm linked assumes edge capacities are integers between 1 and C and that flow and residual capacity values are integral):Scaling-Max-Flow(G, s, t, C) {   foreach e  E f(e)  0     smallest power of 2 greater than or equal to C   G_f  residual graph   while (  1) {      G_f()  -residual graph      while (there exists augmenting path P in G_f()) {         f  augment(f, C, P)         update G_f()      }         / 2   }   return f}Observe that when $\epsilon$ = 1 ($\epsilon = \Delta$ in the psuedocode), you're just finding paths in shortest to longest order, and when $\epsilon$ is large, you're finding paths in (more or less) fattest to slimmest order. In fact, depending on the instance, the capacity-scaling algorithm finds paths in shortest to longest order within buckets of enough flow.Then, add another input parameter $0 \le \rho \le 1$ that represents how much you care about fatness vs shortness. In order to ensure we're not massively affecting the runtime, we further require that $\rho$ is a rational number.Then, each time $\epsilon$ is assigned a value, we additionally take the $\rho$-weighted arithmetic mean (I hope that's the correct term..) between 1 and its current value. That is,$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$For $\rho = 0$, we end up with a pure shortest path algorithm; for $\rho = 1$, we get a pure fattest path algorithm; and for $0 < \rho < 1$ we get something in between. In particular, for some middle value, $\epsilon$ will converge to $\le 1$ more quickly, so you'll get more shortest paths, and fewer fattest paths.