Trouver des chemins courts et gras

Motivation: dans les algorithmes standard de débit maximal de chemin d'augmentation, la boucle interne nécessite de trouver des chemins de la source au puits dans un graphique orienté et pondéré. Théoriquement, il est bien connu que pour que l'algorithme se termine même lorsqu'il existe des capacités de bord irrationnelles, nous devons mettre des restrictions sur les chemins que nous trouvons. L'algorithme Edmonds-Karp, par exemple, nous dit de trouver les chemins les plus courts.

Empiriquement, il a été observé que nous pourrions également vouloir trouver des voies grasses (existe-t-il un meilleur terme pour cela?). Par exemple, lorsque vous utilisez la mise à l'échelle de la capacité , nous trouvons les chemins les plus courts qui peuvent supporter au moins quantité de flux. Il n'y a aucune restriction sur la longueur du chemin. Lorsque nous ne pouvons plus trouver de chemin, nous diminuons ϵ et répétons.$\epsilon$$\epsilon$

Je souhaite optimiser le choix des voies d'augmentation pour une application très spécifique du max-flow, et je souhaite explorer ce compromis entre les voies courtes et les voies grasses. (Remarque: il n'est pas nécessaire pour moi de toujours résoudre le problème. Je suis le plus intéressé à trouver la plus grande limite inférieure d'écoulement dans le temps de mur le plus court.)

Question: Existe - t-il un moyen standard d'interpoler entre l'approche à chemin le plus court et l'approche à échelle de capacité? Autrement dit, existe-t-il un algorithme pour trouver des chemins qui sont à la fois courts et gras, où, idéalement, un paramètre contrôlerait la longueur du chemin que nous sommes prêts à échanger contre le gras? À l'extrême, j'aimerais pouvoir récupérer les chemins les plus courts d'un côté et les chemins de style de mise à l'échelle de la capacité de l'autre.

Dans l'esprit de votre commentaire sur "assez bien mais pas forcément optimal", je vous présente l'idée suivante sans aucune garantie d'optimalité!

Pour être complet, voici le pseudocode auquel vous avez fait référence (Remarque: l'algorithme lié suppose que les capacités de bord sont des entiers compris entre 1 et C et que les valeurs de débit et de capacité résiduelle sont intégrales):

Mise à l'échelle-Max-Flow (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← plus petite puissance de 2 supérieure ou égale à C
   G_f ← graphique résiduel

   tandis que (Δ ≥ 1) {
      G_f (Δ) ← Graphique Δ-résiduel
      tandis que (il existe un chemin croissant P dans G_f (Δ)) {
         f ← ​​augmenter (f, C, P)
         mettre à jour G_f (Δ)
      }
      Δ ← Δ / 2
   }
   retour 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$