Cycle de poids moyen minimum

Entrée : un graphe dirigé pondéré fortement connexe
Sortie : un cycle de poids moyen minimum

Motivation

Le poids moyen d'un cycle est la moyenne sur le poids de ses arêtes.
En général cet algorithme sert comme sous-routine dans des algorithmes pour des problèmes de circulation.
C'est pourquoi dans le code ci-dessous, on reçoit aussi des étiquettes f et b, avec 0<=f<=b, f étant un flot et b une capacité. Puis on ne considère que les arcs pas encore saturées.

Complexité

en O(nm) par l'algorithme de Karp de 1978.

en Python

#!/usr/bin/env python
# c.durr - cnrs, lix - 2010 - Karp s min mean-cost cycle algorithm
 
import sys
from string import *
 
""" A graph is defined as a dictionnary G, mapping a vertex to its neighbors.
    For every arc (u,v) -- so with v in G[u] -- we have the labels
        b[u,v] the capacity of the arc
        f[u,v] the current flow along the arc
        c[u,v] the cost of the arc ( negative profit )
 
    here G_in[v] contains the vertices u such that there is an arc (u,v)
    and G_out[u] contains the vertices v such that there is an arc (u,v)
"""
 
def minMeanCycle(G_in, G_out, f, b, c):
   """ input: graph G, with arc flow, f, arc capacity b and arc cost c.
       output: a cycle in the residual graph of minimal mean cost
       assumes graph is connected and contains at least one vertex
       algorithm by Dick Karp from 1976
       complexity is O(n*m) where n is the number of nodes and m the number of arcs
   """
   V = G_out.keys()      # vertices
   n = len(V)            # number of vertices
   s = V[0]              # arbitrary root
   POSINFTY = ()         # in python ()   is larger  than any number
   NEGINFTY = None       # in python None is smaller than any number
   d = { (0,s): 0 }      # d maps (k,v) to the shortest path from s to v of length k
   p = { (0,s): s }      # p maps (k,v) to the predecessor on that path
 
   for k in range(1,n+1):       # from 1 to n
     for v in V: 
       for u in G_in[v]:        # what is the cost of going to v through pred. u ?
         if (k-1,u) in d:
           alt = d[k-1,u] + c[u,v]
           if (k,v) not in d or d[k,v] > alt:
              d[k,v] = alt
              p[k,v] = u
 
   # read from d the value min_v max_k (d[n,v] - d[k,v]) / (n-k)
   # best contains (value, argmin_v) 
   min_v    = POSINFTY
   argmin_v = s
   for v in V:
      max_k = NEGINFTY
      for k in range(n):     # from 0 to n-1
        if (n,v) in d and (k,v) in d:
           alt = (d[n,v] - d[k,v]) / float(n-k)     # floating point div
           if max_k < alt:
              max_k = alt
      if min_v > max_k and max_k > NEGINFTY:
         min_v = max_k
         argmin_v = v
 
   if min_v == POSINFTY:    # found no cycle at all, 
      return None           # which is impossible if graph is strongly connected
 
   print "argmin_v=", argmin_v
   print "d       =", d
   print "p       =", p
                            # unroll backwards the path from argmin_v to s
                            # and detect any cycle, which must exist by its length
   cycle = []
   j = {}
   v = argmin_v
   for i in range(n, 0, -1):
     u = p[i, v]
     j[v] = len(cycle)
     cycle.append((u,v))
     if u in j:             # detect a cycle through u, keep only suffix
       cycle = cycle[j[u]:]
       cycle.reverse()      # put in normal order
       return cycle
     v = u

Algorithme alternatif

La solution qui suit est moins rapide que celle ci-dessus, mais plus facile à comprendre. Supposons que les poids des arêtes appartiennent à l'intervalle $[w_{min},w_{max}]$, avec $w_{min} < w_{max}$, et que la réponse doit avoir une précision $\epsilon$. La réponse est évidemment entre $w_{min}$ et $w_{max}$, donc on peut la trouver par une recherche dichotomique avec de l'ordre de $\log_{\epsilon}(w_{max} - w_{min})$ itérations, comme suit :

minAvgCycle(G) 
    low := w_min
    high := w_max
    tant que (high - low > eps)
        mid := (low + high)/2
        si G a un cycle de poids moyen < mid
            high = mid
        sinon
            low = mid
    renvoyer mid

Il reste à trouver une façon de déterminer si G a un cycle de poids moyen plus petit qu'une valeur $k$ donnée. Pour cela, on soustrait $k$ du poids de chaque arête. Il est facile de voir que cela entraîne une soustraction de $k$ du poids moyen de chaque cycle. Donc $G$ a un cycle de poids moyen plus petit que $k$ si et seulement si le nouveau graphe $G^{*}$ a un cycle négatif. La détection d'un cycle négatif est un problème beaucoup plus simple, qui peut se résoudre, par exemple, des façons suivantes :

• On ajoute a $G^{*}$ un nouveau sommet $s$, et on met une arête de coût $0$ de $s$ à chaqu'un des autres sommets. Comme tous les cycles sont atteignables à partir de $s$, il suffit d'utiliser l'algorithme de Bellman-Ford. Cela donne une complexité globale $O(nm \log_{\epsilon}(w_{max} - w_{min}) )$.
• On utilise l'algorithme de Floyd-Warshall sur $G^{*}$. Il a un cycle négatif si et seulement si à la fin on trouve un sommet tel que sa distance à lui-même est négative. Cela donne une complexité globale $O(n^3 \log_{\epsilon}(w_{max} - w_{min}) )$.

Références

C'est un classique dans les cours d'algorithmique. il y a beaucoup de notes de cours qui en parlent.

• C'est très bien décrit ici
• A characterization of the minimum cycle mean in a digraph, par Richard M. Karp.