Probleme – Poids $0$ ou $1$ : une file à deux bouts au lieu d'un tas

1. Le rapport. Le parcours en largeur est exactement Dijkstra quand tous les poids valent $1$ : la file joue le rôle d'une file de priorité, parce que les distances sortent déjà triées. On voudrait garder ce bénéfice quand certains arcs coûtent $0$.

L'idée : un arc de poids $0$ ne change pas la distance. Le sommet qu'il découvre appartient donc à la couche courante, et non à la suivante. Il faut pouvoir l'insérer devant.

2. L'algorithme. La réserve devient une file à deux bouts (deque) : on insère devant pour un arc de poids $0$, derrière pour un arc de poids $1$.

/* Distances minimales depuis s, tous les poids valant 0 ou 1.
   d[v] vaut INF si v est inaccessible.
   Preconditions : 0 <= s < n ; adj[u][k].p vaut 0 ou 1.
   Complexite : Theta(n + m) en temps, O(m) en memoire. */
void zero_un(int n, arc* adj[], const int deg[], int s, int d[]) {
    assert(0 <= s && s < n);
    int cap = 2; for (int u = 0; u < n; u = u + 1) { cap = cap + 2 * deg[u]; }
    int* dq = malloc((size_t) cap * sizeof(int));   /* tableau circulaire */
    if (dq == NULL) { return; }
    int tete = cap / 2, queue = cap / 2;            /* la zone utile est [tete, queue) */
    for (int u = 0; u < n; u = u + 1) { d[u] = INF; }
    d[s] = 0; dq[queue] = s; queue = queue + 1;
    /* INVARIANT : les distances des sommets de la deque prennent au plus deux
       valeurs consecutives, et les plus petites sont DEVANT. */
    while (tete < queue) {
        int u = dq[tete]; tete = tete + 1;
        for (int k = 0; k < deg[u]; k = k + 1) {
            int v = adj[u][k].v, p = adj[u][k].p;
            if (d[u] + p < d[v]) {
                d[v] = d[u] + p;
                if (p == 0) { tete = tete - 1; dq[tete] = v; }  /* DEVANT */
                else        { dq[queue] = v; queue = queue + 1; } /* DERRIERE */
            }
        }
    }
    free(dq);
}

Pourquoi deux bouts suffisent. C'est l'invariant écrit dans le code, et c'est le même que celui du parcours en largeur du chapitre, à un détail près : les distances présentes dans la deque prennent au plus deux valeurs consécutives $\delta$ et $\delta +1$, les $\delta$ étant devant. En traitant un sommet de distance $\delta$ :

• un arc de poids $0$ produit un sommet de distance $\delta$, qu'on met devant : il rejoint le bon groupe ;
• un arc de poids $1$ produit un sommet de distance $\delta +1$, qu'on met derrière : idem.

L'invariant est conservé, donc le sommet retiré en tête est toujours de distance minimale — la propriété que Dijkstra obtient par un tas, on l'obtient ici par la structure de l'entrée.

Le dimensionnement de la deque mérite une ligne : un sommet peut y entrer plusieurs fois (une fois par relâchement réussi, donc au plus une fois par arc), et l'on peut pousser devant autant que derrière. Réserver $2m+2$ cases et démarrer au milieu garantit qu'aucun des deux bouts ne déborde. C'est le prix de la simplicité : un tableau circulaire ferait la même chose en $\Theta (n)$ de mémoire, avec un modulo à chaque accès.

3. Complexité et vérification. Chaque arc provoque au plus un ajout et chaque ajout un retrait : $\Theta (n+m)$, comme un parcours en largeur, sans le facteur $\log n$ de Dijkstra. Mesure sur un graphe de six sommets et sept arêtes de poids $0$ ou $1$ :

parcours 0-1 : 0 0 1 1 1 2
Dijkstra     : 0 0 1 1 1 2

Les deux coïncident, et le premier ne construit aucun tas.

Généralisation. Avec des poids entiers bornés par $C$, la même idée donne l'algorithme de Dial : $C+1$ files, indexées par la distance modulo $C+1$, parcourues cycliquement. Complexité $\Theta (nC+m)$, meilleure que Dijkstra dès que $C$ est petit. La leçon est générale : le tas est le prix de l'ignorance sur les poids. Dès qu'on en sait davantage, on paie moins.