Encontrar caminhos curtos e gordos

Motivação: Nos algoritmos padrão de maxflow de caminho de aumento, o loop interno requer a localização de caminhos da origem para afundar em um gráfico direcionado e ponderado. Teoricamente, é sabido que, para que o algoritmo termine mesmo quando há capacidades irracionais de borda, precisamos colocar restrições nos caminhos que encontramos. O algoritmo Edmonds-Karp, por exemplo, nos diz para encontrar caminhos mais curtos.

Empiricamente, foi observado que também podemos querer encontrar caminhos de gordura (existe um termo melhor para isso?). Por exemplo, ao usar o dimensionamento de capacidade , encontramos caminhos mais curtos que podem suportar pelo menos quantidade de fluxo. Não há nenhuma restrição sobre quanto tempo o caminho pode ser. Quando não conseguimos mais encontrar caminhos, diminuímos ϵ e repetimos.$\epsilon$$\epsilon$

Estou interessado em otimizar a escolha de caminhos aumentados para uma aplicação muito específica do fluxo máximo, e quero explorar essa troca entre caminhos curtos e gordos. (Nota: não é necessário que eu sempre resolva o problema. Estou mais interessado em encontrar o maior limite inferior do fluxo no menor período de tempo da parede.)

Pergunta: Existe uma maneira padrão de interpolar entre a abordagem de caminho mais curto e a abordagem de escalonamento de capacidade? Ou seja, existe um algoritmo para encontrar caminhos curtos e gordos, onde, idealmente, algum parâmetro controlaria quanto comprimento do caminho estamos dispostos a trocar por gordura? No extremo, eu gostaria de poder recuperar os caminhos mais curtos de um lado e os de estilo de dimensionamento de capacidade do outro.

No espírito do seu comentário sobre "muito bom, mas não necessariamente ideal", apresento a idéia a seguir com absolutamente nenhuma garantia de otimização!

Para completar, eis o pseudocódigo ao qual você se referiu (Observação: o algoritmo vinculado assume que as capacidades das bordas são números inteiros entre 1 e C e que os valores de capacidade residual e de fluxo são integrais):

Escala-fluxo máximo (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← menor potência de 2 maior ou igual a C
   G_f ← gráfico residual

   enquanto (Δ ≥ 1) {
      G_f (Δ) ← gráfico residual Δ
      while (existe caminho de aumento P em G_f (Δ)) {
         f ← ​​aumento (f, C, P)
         atualizar G_f (Δ)
      }
      Δ ← Δ / 2
   }
   retorno f
}

$\epsilon$$\epsilon = \Delta$$\epsilon$

$0 \le \rho \le 1$$\rho$

$\epsilon$$\rho$

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

$\rho = 0$$\rho = 1$$0 < \rho < 1$$\epsilon$$\le 1$