L'Algorithme de Dijkstra

Le concept du jour : l'algorithme de Dijkstra. Le BFS trouve le plus court chemin en nombre d'arêtes — mais que faire quand les arêtes ont des poids différents ? Quand une route fait 2 km et une autre 50 km ? C'est là qu'intervient Dijkstra. Publié par Edsger W. Dijkstra en 1959, cet algorithme résout le problème du plus court chemin dans un graphe pondéré à poids positifs. C'est littéralement ce que fait votre GPS à chaque trajet.

Le problème : le plus court chemin pondéré

Un graphe pondéré est un graphe où chaque arête porte un coût — une distance, une durée, une latence réseau. Le BFS, qui explore par niveaux, ignore totalement ces poids. Il traite toutes les arêtes comme si elles avaient le même coût unitaire.

Prenons un exemple : pour aller de A à C, il existe deux chemins.

A --1--> B --1--> C
A -------3------> C

Le BFS dirait que les deux chemins "font 2 sauts" versus "1 saut" et choisirait le chemin direct A → C (1 arête). Pourtant, le chemin A → B → C coûte 2 (1 + 1) contre 3 pour A → C directement. Le BFS se trompe. Dijkstra, lui, trouve le bon chemin.

Le principe glouton de Dijkstra

Dijkstra est un algorithme glouton : à chaque étape, il prend la meilleure décision locale disponible sans jamais revenir en arrière. Sa logique repose sur une intuition simple mais puissante.

Il maintient pour chaque nœud une distance provisoire depuis le départ, initialement infinie sauf pour le nœud source (distance 0). À chaque itération :

1. On choisit le nœud non encore traité avec la distance provisoire la plus faible.
2. On le marque comme "traité" : sa distance est maintenant définitive.
3. Pour chacun de ses voisins, on calcule si passer par ce nœud offre un chemin plus court. Si oui, on met à jour leur distance provisoire. C'est la phase de relaxation.

L'invariant fondamental : une fois qu'un nœud est marqué traité, sa distance est définitivement optimale. C'est la propriété qui permet à l'algorithme de fonctionner sans jamais reconsidérer ses décisions passées — à condition que tous les poids soient positifs.

Exemple pas à pas

Considérons ce graphe :

     2       3
A -------> B -------> D
|          |          ^
|    5     | 1        | 1
+--------> C ---------+

Nœuds : A, B, C, D. Arêtes (dirigées) : A→B (2), A→C (5), B→C (1), B→D (3), C→D (1).

Initialisation : distances = { A: 0, B: ∞, C: ∞, D: ∞ }. Non traités : {A, B, C, D}.

Étape 1 : On choisit A (distance 0, la plus faible). On relaxe ses voisins.

• A→B : 0 + 2 = 2 < ∞ → dist[B] = 2
• A→C : 0 + 5 = 5 < ∞ → dist[C] = 5
• Distances : { A: 0✓, B: 2, C: 5, D: ∞ }

Étape 2 : On choisit B (distance 2). On relaxe ses voisins.

• B→C : 2 + 1 = 3 < 5 → dist[C] = 3 (mise à jour !)
• B→D : 2 + 3 = 5 < ∞ → dist[D] = 5
• Distances : { A: 0✓, B: 2✓, C: 3, D: 5 }

Étape 3 : On choisit C (distance 3). On relaxe ses voisins.

• C→D : 3 + 1 = 4 < 5 → dist[D] = 4 (mise à jour !)
• Distances : { A: 0✓, B: 2✓, C: 3✓, D: 4 }

Étape 4 : On choisit D (distance 4). Plus de voisins à relaxer.

• Distances finales : { A: 0, B: 2, C: 3, D: 4 }

Le plus court chemin de A à D est A → B → C → D pour un coût de 4, et non A → B → D (coût 5) ni A → C → D (coût 6).

Implémentation TypeScript

La clé de performance de Dijkstra est la structure utilisée pour extraire à chaque étape le nœud de distance minimale. L'idéal est un tas min (min-heap) ou une file de priorité. Voici une implémentation avec une priority queue simplifiée.

type Edge = { to: string; weight: number };
type Graph = Map<string, Edge[]>;
 
// File de priorité minimale (min-heap simplifié avec tableau trié)
// Pour la production, préférer une vraie implémentation de tas binaire
class MinPriorityQueue {
  private items: { node: string; priority: number }[] = [];
 
  enqueue(node: string, priority: number): void {
    this.items.push({ node, priority });
    // On maintient le tableau trié par priorité croissante
    this.items.sort((a, b) => a.priority - b.priority);
  }
 
  dequeue(): { node: string; priority: number } | undefined {
    return this.items.shift();
  }
 
  get isEmpty(): boolean {
    return this.items.length === 0;
  }
}
 
function dijkstra(
  graph: Graph,
  start: string
): Map<string, number> {
  const distances = new Map<string, number>();
  const visited = new Set<string>();
  const pq = new MinPriorityQueue();
 
  // Initialisation : distance infinie pour tous les nœuds
  for (const node of graph.keys()) {
    distances.set(node, Infinity);
  }
  distances.set(start, 0);
  pq.enqueue(start, 0);
 
  while (!pq.isEmpty) {
    const current = pq.dequeue()!;
 
    // Si déjà traité définitivement, on ignore
    if (visited.has(current.node)) continue;
    visited.add(current.node);
 
    // Phase de relaxation : on explore chaque voisin
    for (const edge of graph.get(current.node) ?? []) {
      if (visited.has(edge.to)) continue;
 
      const newDist = distances.get(current.node)! + edge.weight;
 
      if (newDist < distances.get(edge.to)!) {
        distances.set(edge.to, newDist);
        pq.enqueue(edge.to, newDist);
      }
    }
  }
 
  return distances;
}
 
// Exemple avec le graphe de la démonstration
const graph: Graph = new Map([
  ["A", [{ to: "B", weight: 2 }, { to: "C", weight: 5 }]],
  ["B", [{ to: "C", weight: 1 }, { to: "D", weight: 3 }]],
  ["C", [{ to: "D", weight: 1 }]],
  ["D", []],
]);
 
const distances = dijkstra(graph, "A");
console.log(distances);
// Map { 'A' => 0, 'B' => 2, 'C' => 3, 'D' => 4 }

Reconstruire le chemin

La fonction ci-dessus retourne les distances minimales depuis le nœud de départ. Pour récupérer le chemin lui-même, on ajoute une map previous qui mémorise le nœud précédent sur le chemin optimal :

function dijkstraWithPath(
  graph: Graph,
  start: string,
  end: string
): { distance: number; path: string[] } {
  const distances = new Map<string, number>();
  const previous = new Map<string, string | null>();
  const visited = new Set<string>();
  const pq = new MinPriorityQueue();
 
  for (const node of graph.keys()) {
    distances.set(node, Infinity);
    previous.set(node, null);
  }
  distances.set(start, 0);
  pq.enqueue(start, 0);
 
  while (!pq.isEmpty) {
    const current = pq.dequeue()!;
    if (visited.has(current.node)) continue;
    visited.add(current.node);
 
    if (current.node === end) break;
 
    for (const edge of graph.get(current.node) ?? []) {
      if (visited.has(edge.to)) continue;
      const newDist = distances.get(current.node)! + edge.weight;
 
      if (newDist < distances.get(edge.to)!) {
        distances.set(edge.to, newDist);
        previous.set(edge.to, current.node);
        pq.enqueue(edge.to, newDist);
      }
    }
  }
 
  // Reconstruction du chemin depuis la fin
  const path: string[] = [];
  let current: string | null = end;
 
  while (current !== null) {
    path.unshift(current);
    current = previous.get(current) ?? null;
  }
 
  return { distance: distances.get(end)!, path };
}
 
const result = dijkstraWithPath(graph, "A", "D");
console.log(result);
// { distance: 4, path: ['A', 'B', 'C', 'D'] }

Complexité

Avec V le nombre de sommets et E le nombre d'arêtes. Pour la majorité des graphes peu denses (E ≪ V²), l'implémentation avec tas binaire est la plus courante en pratique. Notre MinPriorityQueue basée sur un tableau trié est en O(V²) — correcte pour illustrer le concept, mais à remplacer par un vrai tas pour la production.

Les limites : pourquoi pas Bellman-Ford ?

Dijkstra a une contrainte fondamentale : il ne fonctionne pas avec des poids négatifs. Pourquoi ? Parce que son invariant suppose que lorsqu'un nœud est marqué traité, sa distance est définitive. Un poids négatif pourrait créer un chemin encore plus court via un nœud déjà traité, invalidant cette garantie.

Exemple : A→B (3), A→C (2), C→B (-5). Dijkstra traiterait B à distance 3, mais le vrai chemin optimal est A→C→B = 2 + (-5) = -3.

Dans ce cas, on se tourne vers Bellman-Ford : plus lent en O(V × E), mais capable de gérer les poids négatifs — et même de détecter les cycles de poids négatif (des boucles qui réduisent indéfiniment le coût, rendant le problème sans solution).

Cas d'usage concrets

Navigation GPS : c'est l'application emblématique. Google Maps, Waze, Apple Plans utilisent tous des variantes de Dijkstra (souvent combinées à A* pour les très grands graphes). Les nœuds sont les intersections, les arêtes sont les routes avec leurs distances ou temps de parcours, et le poids tient compte du trafic en temps réel.

Protocoles de routage réseau : OSPF (Open Shortest Path First), l'un des protocoles de routage Internet les plus répandus, est une implémentation directe de Dijkstra. Chaque routeur calcule l'arbre des plus courts chemins vers tous les autres nœuds du réseau pour construire sa table de routage.

Jeux vidéo et IA de déplacement : les personnages non-joueurs (PNJ) qui naviguent dans un environnement utilisent fréquemment Dijkstra ou A* (une extension heuristique de Dijkstra) pour trouver leur chemin vers une cible tout en évitant les obstacles.

Réseaux de télécommunications : minimiser la latence ou maximiser la bande passante dans un réseau de fibres optiques, calculer les chemins de secours en cas de panne — autant de problèmes de plus court chemin pondéré résolus avec Dijkstra.

Finance et logistique : optimiser les flux dans des réseaux de distribution, calculer les arbitrages de devises (avec des logarithmes pour transformer les multiplications en additions), planifier des itinéraires de livraison — Dijkstra opère souvent en coulisses.

L'algorithme de Dijkstra est l'un de ces fondamentaux qui perdurent depuis plus de soixante ans sans prendre une ride. Sa logique gloutonne — toujours choisir le meilleur nœud disponible, relaxer ses voisins, ne jamais revenir en arrière — est à la fois simple à comprendre et redoutablement efficace. Comprendre Dijkstra, c'est comprendre comment Internet route vos paquets et comment votre GPS recalcule l'itinéraire en temps réel.