Les graphes pondérés

Les algorithmes de parcours du chapitre précédent traitaient des graphes non pondérés, où chaque arête a la même valeur. Mais il existe tout un univers parallèle de problèmes pour les graphes pondérés (weighted graphs) : les arêtes d'un réseau routier portent naturellement des valeurs numériques — coût de construction, temps de trajet, longueur, limite de vitesse. Trouver le plus court chemin dans un tel graphe se révèle bien plus subtil qu'un simple parcours en largeur, mais ouvre la porte à une foule d'applications.

Skiena insiste sur un point qui structure tout le chapitre : ces problèmes d'optimisation — arbre couvrant minimal, plus courts chemins, flot maximum — se résolvent efficacement, ce qui est en soi remarquable. Rappelez-vous que le tout premier problème de graphe pondéré rencontré dans le livre, le voyageur de commerce, n'admet, lui, aucun algorithme efficace connu. Nous travaillerons sur une liste d'adjacence où chaque arête sortante de x porte désormais un poids explicite.

L'arbre couvrant minimal

Un arbre couvrant (spanning tree) d'un graphe G = (V, E) est un sous-ensemble d'arêtes formant un arbre qui connecte tous les sommets. Pour un graphe pondéré, on s'intéresse à l'arbre couvrant minimal (minimum spanning tree, ou MST) : celui dont la somme des poids d'arêtes est la plus petite possible.

C'est la réponse chaque fois qu'on doit relier un ensemble de points — villes, maisons, jonctions — avec le moins de câble, de route ou de tuyau possible. Tout arbre est le plus petit graphe connexe en nombre d'arêtes ; le MST est le plus petit en poids total. Deux algorithmes gloutons (greedy) le construisent, et tous deux démontrent qu'une heuristique gloutonne bien choisie peut atteindre l'optimum global.

L'algorithme de Prim

L'algorithme de Prim part d'un sommet quelconque et fait croître l'arbre, une arête à la fois, jusqu'à inclure tous les sommets. À chaque itération, il choisit l'arête de poids minimal reliant un sommet dans l'arbre à un sommet hors de l'arbre.

Prim-MST(G)
  Choisir un sommet de départ s.
  Tant qu'il reste des sommets hors de l'arbre :
    Sélectionner l'arête de poids minimal entre
    un sommet de l'arbre et un sommet hors arbre.
    Ajouter cette arête et ce sommet à l'arbre.

Pourquoi le résultat est-il bien minimal ? Par l'absurde : supposez qu'au moment d'insérer l'arête (x, y), l'arbre construit soit encore un sous-arbre d'un MST Tmin, mais que ce choix nous en écarte fatalement. Il existe alors dans Tmin un chemin de x à y qui emprunte une arête (v1, v2) reliant l'arbre à l'extérieur. Cette arête a forcément un poids au moins égal à celui de (x, y), sinon Prim l'aurait choisie d'abord. Échanger les deux donne un arbre couvrant pas plus lourd : Prim n'a donc pas commis d'erreur fatale.

L'implémentation naïve, qui balaie toutes les arêtes à chaque tour, coûte O(mn). Plus malin : on garde pour chaque sommet hors arbre le coût de la plus légère arête connue qui l'y relie. À chaque insertion, seules les arêtes sortant du dernier sommet ajouté peuvent améliorer ces coûts. Avec un drapeau « dans l'arbre » par sommet, on teste en temps constant si une arête joint l'intérieur à l'extérieur.

type Edge = { to: number; weight: number };
type Graph = Edge[][]; // liste d'adjacence indexée par sommet

// Prim avec tableau de distances. Complexité : O(n^2).
function prim(g: Graph, start: number): number[] {
  const n = g.length;
  const inTree = new Array<boolean>(n).fill(false);
  const dist = new Array<number>(n).fill(Infinity);
  const parent = new Array<number>(n).fill(-1);
  dist[start] = 0;
  let v = start;

  while (!inTree[v]) {
    inTree[v] = true;
    for (const e of g[v]) {
      if (!inTree[e.to] && dist[e.to] > e.weight) {
        dist[e.to] = e.weight; // coût pour rattacher e.to
        parent[e.to] = v;
      }
    }
    // Chercher le sommet hors arbre le plus proche.
    let best = Infinity;
    for (let i = 0; i < n; i++) {
      if (!inTree[i] && dist[i] < best) {
        best = dist[i];
        v = i;
      }
    }
  }
  return parent; // l'arbre est encodé par les parents
}

L'algorithme de Kruskal

L'algorithme de Kruskal aborde le problème par l'autre bout et se révèle plus efficace sur les graphes creux (sparse). Au lieu de partir d'un sommet, il fait croître des composantes connexes. Initialement, chaque sommet est sa propre composante. On considère les arêtes par poids croissant ; si les deux extrémités sont dans des composantes différentes, on insère l'arête et on fusionne les composantes. Sinon, l'arête créerait un cycle : on la jette. Puisque chaque composante est toujours un arbre, on n'a jamais besoin de tester explicitement les cycles.

Kruskal-MST(G)
  Mettre les arêtes dans une file ordonnée par poids.
  count = 0
  Tant que count < n - 1 :
    Prendre l'arête suivante (v, w).
    Si composante(v) != composante(w) :
      Ajouter (v, w) à l'arbre.
      Fusionner composante(v) et composante(w).

La preuve d'optimalité est la même que pour Prim. Côté coût : trier les m arêtes prend O(m log m). La boucle teste m fois la connexité de deux composantes. Avec un parcours BFS/DFS naïf, ce test coûte O(n), d'où un O(mn) médiocre. La clé est une structure capable de répondre à ces requêtes en O(log n) : union-find.

// Kruskal sur une liste d'arêtes. O(m log m) avec union-find.
type WEdge = { x: number; y: number; weight: number };

function kruskal(n: number, edges: WEdge[]): WEdge[] {
  const uf = new UnionFind(n);
  const sorted = [...edges].sort((a, b) => a.weight - b.weight);
  const mst: WEdge[] = [];
  for (const e of sorted) {
    if (!uf.sameComponent(e.x, e.y)) {
      mst.push(e);
      uf.union(e.x, e.y);
      if (mst.length === n - 1) break;
    }
  }
  return mst;
}

Union-find : les ensembles disjoints

La structure union-find (aussi dite ensembles disjoints, disjoint sets) maintient une partition d'un univers d'éléments et supporte efficacement deux opérations :

• find(i) — trouver la racine (le nom) de l'ensemble contenant i, en remontant les pointeurs parents jusqu'au sommet sans parent ;
• union(i, j) — relier la racine d'un arbre à celle de l'autre, de sorte que find(i) === find(j) désormais.

Chaque ensemble est représenté par un arbre « à l'envers » : chaque nœud pointe vers son parent, et le nom de l'ensemble est la clé de la racine. Pour que les arbres restent peu profonds, on applique deux optimisations. L'union par rang (ou par taille) attache toujours le plus petit arbre sous le plus grand : la hauteur n'augmente que pour les nœuds du petit arbre, c'est-à-dire le plus petit nombre possible. La compression de chemin (path compression) rebranche, lors d'un find, chaque nœud traversé directement sur la racine.

// Union-find avec union par taille + compression de chemin.
class UnionFind {
  private parent: number[];
  private size: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array<number>(n).fill(1);
  }

  // Remonte jusqu'à la racine en aplatissant le chemin.
  find(x: number): number {
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root];
    while (this.parent[x] !== root) {
      const next = this.parent[x];
      this.parent[x] = root; // compression
      x = next;
    }
    return root;
  }

  union(a: number, b: number): void {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra; // le petit sous le grand
    this.size[ra] += this.size[rb];
  }

  sameComponent(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

Pourquoi est-ce efficace ? Avec l'union par taille, il faut doubler le nombre de nœuds d'un arbre pour gagner une unité de hauteur. On ne peut doubler que log₂ n fois avant d'épuiser les n éléments : find et union sont donc en O(log n), ce qui suffit largement à Kruskal. Skiena note qu'on peut faire encore mieux (quasi constant amorti) avec la compression de chemin.

War story : « Nothing but Nets »

Une petite entreprise de test de circuits imprimés voulait accélérer un robot à deux bras qui vérifie la connectivité des « nets » (ensembles de points reliés par une couche métallique). Skiena reconnaît d'abord un voyageur de commerce caché dans le mouvement des bras, puis comprend que l'enjeu réel est de découper chaque gros net en petits morceaux qui se chevauchent par un point. C'est un problème de partitionnement (clustering) — et le MST en est l'outil classique : on calcule l'arbre couvrant minimal des points du net, puis on le casse en grappes dès qu'une arête devient trop longue. Chaque grappe partage exactement un point avec sa voisine, garantissant la connexité. Bonus de modélisation : comme le robot bouge ses deux moteurs simultanément, le bon poids d'arête n'est pas la distance euclidienne mais la métrique L∞ (le plus grand écart en x ou y). Résultat : 30 % de trajet en moins. La leçon de Skiena : la plupart des applications de graphes se ramènent à des propriétés standard — MST, plus courts chemins — pour lesquelles des algorithmes éprouvés existent déjà.

Les plus courts chemins

Dans un graphe non pondéré, le plus court chemin de s à t se trouve par un simple parcours en largeur. Mais le BFS ne suffit plus en pondéré : le chemin le plus court en poids peut emprunter beaucoup d'arêtes, exactement comme le trajet le plus rapide entre la maison et le bureau peut passer par d'astucieux raccourcis de campagne.

Dijkstra : poids positifs

L'algorithme de Dijkstra est la méthode de référence dès qu'on cherche les plus courts chemins depuis une source unique dans un graphe à poids positifs. Depuis s, il trouve le plus court chemin vers tous les autres sommets, définissant un arbre des plus courts chemins enraciné en s.

L'idée repose sur une observation de type programmation dynamique (dynamic programming) : si le plus court chemin de s à t passe par un sommet intermédiaire x, alors son préfixe de s à x doit lui-même être le plus court chemin de s à x. On calcule donc les distances dans l'ordre croissant. À chaque tour, on fige le sommet inconnu de distance minimale, puis on relâche (relax) ses arêtes sortantes : pour chaque arête (v, x), on teste si passer par v raccourcit dist[x].

C'est presque exactement Prim : la seule différence est le critère de désirabilité. Prim ne regarde que le poids de la prochaine arête ; Dijkstra veut le sommet le plus proche de la source, ce qui combine le poids de l'arête et la distance déjà accumulée jusqu'au sommet d'attache.

// Dijkstra avec min-heap. O((n + m) log n).
function dijkstra(g: Graph, start: number): number[] {
  const n = g.length;
  const dist = new Array<number>(n).fill(Infinity);
  const done = new Array<boolean>(n).fill(false);
  dist[start] = 0;
  const heap = new MinHeap();
  heap.push(start, 0);

  while (!heap.isEmpty()) {
    const [v, d] = heap.pop();
    if (done[v]) continue; // doublon obsolète dans le tas
    done[v] = true;
    for (const e of g[v]) {
      // Relâchement de l'arête (v, e.to).
      if (d + e.weight < dist[e.to]) {
        dist[e.to] = d + e.weight;
        heap.push(e.to, dist[e.to]);
      }
    }
  }
  return dist;
}

// Min-heap binaire minimal : (sommet, priorité).
class MinHeap {
  private h: [number, number][] = [];
  isEmpty(): boolean { return this.h.length === 0; }

  push(v: number, p: number): void {
    this.h.push([v, p]);
    let i = this.h.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.h[parent][1] <= this.h[i][1]) break;
      [this.h[parent], this.h[i]] = [this.h[i], this.h[parent]];
      i = parent;
    }
  }

  pop(): [number, number] {
    const top = this.h[0];
    const last = this.h.pop()!;
    if (this.h.length > 0) {
      this.h[0] = last;
      let i = 0;
      const n = this.h.length;
      for (;;) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let m = i;
        if (l < n && this.h[l][1] < this.h[m][1]) m = l;
        if (r < n && this.h[r][1] < this.h[m][1]) m = r;
        if (m === i) break;
        [this.h[m], this.h[i]] = [this.h[i], this.h[m]];
        i = m;
      }
    }
    return top;
  }
}

Bellman-Ford : gérer les poids négatifs

Quand des arêtes peuvent être négatives, on passe à Bellman-Ford. L'idée : relâcher toutes les arêtes, n − 1 fois de suite. Comme tout plus court chemin sans cycle compte au plus n − 1 arêtes, après n − 1 passes les distances sont stabilisées. Une n-ième passe qui améliorerait encore une distance trahit la présence d'un cycle de poids négatif — auquel cas il n'existe pas de plus court chemin bien défini (on pourrait tourner indéfiniment pour diminuer le coût).

// Bellman-Ford. O(V * E). Détecte les cycles négatifs.
function bellmanFord(
  n: number, edges: WEdge[], start: number,
): number[] | null {
  const dist = new Array<number>(n).fill(Infinity);
  dist[start] = 0;
  for (let pass = 0; pass < n - 1; pass++) {
    for (const e of edges) {
      if (dist[e.x] + e.weight < dist[e.y]) {
        dist[e.y] = dist[e.x] + e.weight; // relâchement
      }
    }
  }
  // Une amélioration de plus => cycle négatif atteignable.
  for (const e of edges) {
    if (dist[e.x] + e.weight < dist[e.y]) return null;
  }
  return dist;
}

C'est précisément ce dont on a besoin pour des problèmes comme l'arbitrage de devises (un cycle de produit de taux supérieur à 1 devient un cycle de somme de logarithmes négatifs).

Floyd-Warshall : toutes les paires

Pour connaître le centre d'un graphe, son diamètre (le plus long des plus courts chemins), ou simplement la distance entre toutes les paires de sommets, on pourrait lancer Dijkstra depuis chaque sommet. Mais Floyd-Warshall offre une méthode d'une élégance redoutable, fondée sur la programmation dynamique sur la matrice d'adjacence.

On numérote les sommets de 1 à n. Soit W[i][j]ᵏ la longueur du plus court chemin de i à j n'utilisant comme intermédiaires que les sommets 1..k. Pour k = 0, aucun intermédiaire : c'est la matrice d'adjacence initiale (avec Infinity pour les non-arêtes — surtout pas 0, qui offrirait un trajet gratuit). À chaque itération, on autorise un nouvel intermédiaire k, utile seulement s'il existe un meilleur chemin passant par lui :

W[i][j]ᵏ = min( W[i][j]ᵏ⁻¹ ,
                W[i][k]ᵏ⁻¹ + W[k][j]ᵏ⁻¹ )

La traduction tient en une triple boucle d'une simplicité désarmante :

// Floyd-Warshall. O(n^3). w mutée sur place ; w[i][j] = Infinity
// si pas d'arête, w[i][i] = 0.
function floydWarshall(w: number[][]): void {
  const n = w.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const through = w[i][k] + w[k][j];
        if (through < w[i][j]) w[i][j] = through;
      }
    }
  }
}

En O(n³), Floyd-Warshall n'est asymptotiquement pas meilleur que n appels à Dijkstra, mais ses boucles sont si serrées qu'il l'emporte souvent en pratique. C'est l'un des rares algorithmes de graphe qui préfère la matrice d'adjacence à la liste. Il sert aussi à calculer la fermeture transitive (transitive closure) : après son passage, toute paire (i, j) dont la distance reste Infinity n'est tout simplement pas joignable.

Algorithme	Hypothèse sur les poids	Portée	Complexité	Usage
BFS	non pondéré	source unique	O(n + m)	tout poids égal
Dijkstra	positifs uniquement	source unique	O((n + m) log n)	cas le plus courant
Bellman-Ford	négatifs autorisés	source unique	O(n · m)	détecte les cycles négatifs
Floyd-Warshall	pas de cycle négatif	toutes les paires	O(n³)	diamètre, centre, fermeture

Flots de réseau et couplage biparti

Un graphe pondéré peut se lire comme un réseau de tuyaux, le poids de l'arête (i, j) donnant la capacité du tuyau. Le problème du flot maximum (maximum flow) demande la plus grande quantité de flux qu'on puisse envoyer d'une source s à un puits t en respectant chaque capacité.

Les algorithmes classiques reposent sur les chemins augmentants (augmenting paths), idée due à Ford et Fulkerson : on cherche répétitivement un chemin de capacité positive de s à t et on l'ajoute au flot. On peut prouver qu'un flot est optimal si et seulement s'il ne reste aucun chemin augmentant. La structure clé est le graphe résiduel R(G, f) : pour chaque arête (i, j) de capacité c portant un flot f, il contient une arête directe de capacité résiduelle c − f (s'il en reste) et une arête inverse (j, i) de capacité f (permettant d'annuler du flux déjà poussé). Un chemin de s à t dans le résiduel signifie qu'on peut encore pousser du flux ; le minimum des capacités le long du chemin donne le volume supplémentaire.

netflow(G, s, t)
  Ajouter les arêtes résiduelles à G.
  Trouver un chemin augmentant par BFS depuis s.
  Tant qu'un tel chemin existe (volume > 0) :
    Augmenter le chemin du volume = min des résidus.
    Rechercher un nouveau chemin par BFS.

En choisissant toujours le chemin augmentant le plus court (un BFS, donc), on obtient l'algorithme d'Edmonds-Karp, qui garantit O(n³) augmentations suffisantes.

Application : le couplage biparti

L'importance première du flot est de résoudre d'autres problèmes. Le cas classique est le couplage biparti (bipartite matching). Un couplage est un ensemble d'arêtes ne partageant aucun sommet ; il apparie certains sommets, chacun dans au plus une paire. Un graphe est biparti si ses sommets se divisent en deux ensembles L et R, toute arête ayant une extrémité de chaque côté — pensez à des emplois (L) et des personnes capables de les faire (R).

Le plus grand couplage se trouve par flot maximum : on crée une source s reliée à chaque sommet de L par une arête de capacité 1, un puits t relié à chaque sommet de R de même, et on donne aussi le poids 1 à chaque arête du graphe biparti. Le flot maximum de s à t définit alors le plus grand couplage — impossible de faire passer plus d'une unité de flux par un sommet, donc impossible de l'apparier deux fois.

Concevoir des graphes, pas des algorithmes

Le secret, martèle Skiena, est d'apprendre à concevoir des graphes, pas des algorithmes. Nous l'avons déjà vu : l'arbre couvrant maximal s'obtient en niant les poids puis en lançant le MST ; le couplage biparti se résout en fabriquant un graphe de flot ad hoc. Chaque fois qu'un problème réel se présente, l'effort doit porter sur la modélisation — quels sont les sommets, les arêtes, les poids ? — pour le ramener à un problème classique. La war story « Dialing for Documents » l'illustre : reconstruire un texte tapé au clavier téléphonique devient un plus court chemin dans un graphe où chaque interprétation possible d'une phrase est un chemin, les poids d'arêtes encodant la vraisemblance grammaticale (c'est, au fond, l'algorithme de Viterbi sur un DAG).

À retenir

• Arbre couvrant minimal : Prim fait croître un arbre depuis un sommet (idéal sur graphes denses, O(m + n log n) avec un tas) ; Kruskal trie les arêtes et fusionne des composantes via union-find (idéal sur graphes creux, O(m log m)).
• Union-find : ensembles disjoints avec union par taille et compression de chemin ; find et union en O(log n), le cœur de l'efficacité de Kruskal.
• Dijkstra : source unique, poids positifs seulement, O((n + m) log n) avec un min-heap ; quasi identique à Prim, mais on minimise la distance à la source.
• Bellman-Ford gère les poids négatifs et détecte les cycles négatifs en O(n · m) ; Floyd-Warshall calcule toutes les paires en O(n³) par une triple boucle, et fait la fermeture transitive.
• Flot maximum par chemins augmentants (Ford-Fulkerson, Edmonds-Karp) sur le graphe résiduel ; le flot max égale la coupe minimale.
• Modélisez, ne réinventez pas : ramenez votre problème à un MST, un plus court chemin ou un flot — le couplage biparti se résout ainsi par flot maximum.