Plus courts chemins : Dijkstra et au-delà

Invariant : à chaque tour, (i) pour tout sommet figé $f$, $\text{dist}[f]=\delta (\text{source},f)$ ; (ii) pour tout sommet non figé $x$, $\text{dist}[x]$ est le poids du meilleur chemin de la source à $x$ dont tous les sommets intermédiaires sont figés. L'initialisation est claire ($\text{dist}[\text{source}]=0$, le reste $\infty$).

Le pas crucial : soit $s$ le sommet promu (minimum des provisoires). Supposons par l'absurde qu'un chemin $C$ strictement meilleur que $\text{dist}[s]$ existe de la source vers $s$. Ce chemin quitte à un moment la zone figée : soit $(u,v)$ son premier arc avec $u$ figé et $v$ non figé. Alors :

$$\text{dist}[v]\underset{\text{(ii)}}{\le }\delta (\text{source},u)+p(u,v)\le \text{poids}(C)<\text{dist}[s],$$

la deuxième inégalité parce que le reste du chemin $C$, de $v$ jusqu'à $s$, a un poids positif ou nul — c'est ici, et seulement ici, que la positivité des poids travaille. Mais $\text{dist}[v]<\text{dist}[s]$ contredit le choix de $s$ comme minimum. Donc $\text{dist}[s]=\delta (\text{source},s)$ : (i) s'étend à $s$. La mise à jour des voisins de $s$ rétablit (ii), et l'invariant se propage. Terminaison : chaque tour fige un sommet — variant : le cardinal de a_traiter.

Init : Paris $0$, le reste $\infty$. Tour 1 : Paris figé ; relâchements — Lyon $465$, Lille $225$, Nantes $385$. Tour 2 : minimum Lille ($225$), figée ; son seul voisin Paris est figé : rien. Tour 3 : Nantes ($385$) figée ; rien de mieux. Tour 4 : Lyon ($465$) figé ; relâchement — Marseille $465+315=780$. Tour 5 : Marseille ($780$) figée. Distances finales : Lille $225$, Nantes $385$, Lyon $465$, Marseille $780$ ; chemin vers Marseille par les pères : Paris $\to$ Lyon $\to$ Marseille. (Observer l'ordre des figés : par distance croissante à Paris, exactement comme le BFS figeait par nombre d'arêtes croissant — Dijkstra est un BFS qui a appris l'arithmétique.)

Au tour 1, $a$ reçoit la provisoire $7$ (la route directe). Au tour 2, $b$ — provisoire $2$, plus petite que celle de $a$ — est figé en premier, et son relâchement découvre $2+3=5<7$ : la provisoire de $a$ est améliorée, et son père bascule de $s$ à $b$. C'est tout le mécanisme : tant qu'un sommet n'est pas figé, sa provisoire reste contestable, et l'extraction par minimum garantit qu'on fige $b$ (qui peut offrir des raccourcis) avant $a$ (qui en bénéficie). Si l'on figeait $a$ d'abord — par exemple en traitant les sommets dans un ordre arbitraire — sa distance serait gelée à $7$, fausse : c'est précisément l'erreur que commet Dijkstra sur poids négatifs, où le « bon ordre » n'existe plus. (Le contre-exemple négatif du cours et cet exercice sont le même phénomène, vu des deux côtés de l'hypothèse.)

def table_des_routes(R: dict, source) -> None:
    dist, pere = dijkstra(R, source)
    for v in sorted(R, key=lambda x: dist[x]):
        if dist[v] == float("inf"):
            print(v, ": inaccessible")
        elif v != source:
            c = chemin(pere, source, v)          # chapitre 13
            print(v, ":", dist[v], "via", " -> ".join(map(str, c)))

Le tri par distance croissante reconstitue l'ordre des figés — agréable à lire et gratuit. Une seule exécution de Dijkstra livre les chemins vers toutes les destinations : l'algorithme est « une source vers tous », et c'est l'arbre des pères, construit en passant, qui contient toutes les routes. (L'arbre des pères de Dijkstra est l'analogue pondéré de l'arbre du BFS : un arbre couvrant des plus courts chemins — au sens du chapitre 13, un vrai arbre : $n-1$ arcs, pas de cycle.)

def dijkstra_sur(R: dict, source):
    assert all(R[u][v] >= 0 for u in R for v in R[u]), "poids négatif !"
    return dijkstra(R, source)

pieges = {"s": {"a": 2, "b": 3}, "a": {}, "b": {"a": -2}}
dist, _ = dijkstra(pieges, "s")
assert dist["a"] == 2            # FAUX silencieusement : la vraie distance est 1 !
# dijkstra_sur(pieges, "s")      # AssertionError: poids négatif ! — l'arrêt propre

(a) L'exécution nue déroule sans broncher : $a$ (provisoire $2$) est figé avant $b$ (provisoire $3$), et le relâchement $b\to a$ arrive trop tard — dist["a"] vaut $2$, la vérité est $3-2=1$. Aucun message : c'est l'erreur de logique du chapitre 1 dans toute sa noirceur, une précondition violée qui fait mentir le résultat (le parallèle exact de la dichotomie sur tableau non trié, chapitre 5). (b) L'assertion coûte $O(m)$ — négligeable devant $O(n^2)$ — et transforme le mensonge en arrêt immédiat et localisé. (Règle de conception : quand la correction d'un algorithme repose sur une hypothèse que l'appelant peut violer sans s'en douter, l'hypothèse mérite une assertion — le théorème du cours dit précisément où Dijkstra a le droit de mentir.)

BFS : $t$ est à distance $1$ (une étape, l'arc direct). Dijkstra : $\text{dist}[t]=2$ via $a$ — les deux réponses sont « justes », elles ne mesurent pas la même chose (chapitre 12 : choisir ce que mesure le poids est un acte de modélisation).

Règle générale : à poids tous égaux à $1$, le poids d'un chemin est son nombre d'arcs — les deux notions de distance coïncident par définition. Et les algorithmes aussi : dans Dijkstra, les provisoires ne prennent que des valeurs entières $d$ ou $d+1$ quand on traite les sommets de distance $d$ ; l'extraction du minimum sert alors les sommets exactement dans l'ordre où une file FIFO les aurait servis — Dijkstra dégénère en BFS, en payant $O(n^2)$ ce que la file faisait en $O(n+m)$. (D'où la règle pratique : poids uniformes $\Rightarrow$ BFS, jamais Dijkstra — savoir reconnaître le cas particulier où l'outil simple suffit est aussi une compétence d'analyse.)

# Ligne 1 : A1 - B1 - C1 ; ligne 2 : D2 - B2 - E2 ; correspondance en B
M = {"A1": {"B1": 2}, "B1": {"A1": 2, "C1": 2, "B2": 5},
     "C1": {"B1": 2},
     "D2": {"B2": 2}, "B2": {"D2": 2, "E2": 2, "B1": 5},
     "E2": {"B2": 2}}

dist, pere = dijkstra(M, "A1")
assert dist["C1"] == 4            # A1 -> B1 -> C1 : sans correspondance
assert dist["E2"] == 9            # A1 -> B1 -> (corresp. 5) -> B2 -> E2
assert chemin(pere, "A1", "E2") == ["A1", "B1", "B2", "E2"]

Le trajet vers E2 paie ses $5$ minutes de correspondance — c'est le dédoublement des stations qui rend ce coût exprimable : sans lui, « être à B » serait un seul sommet et changer de ligne serait gratuit, faussant tous les itinéraires. (Vérifier ensuite la sensibilité du modèle : passer la correspondance à $1$ minute, ou ajouter une ligne directe concurrente, et regarder les chemins basculer — un modèle se valide en le secouant, pas seulement en le lisant. C'est exactement ainsi que les calculateurs d'itinéraires réels arbitrent « le plus court » contre « le moins de changements » : en réglant des poids.)

def chemin_du_goulot(R: dict, source) -> dict:
    """cap[v] = la plus grande capacité de goulot d'un chemin source -> v."""
    cap = {s: 0 for s in R}
    cap[source] = float("inf")               # rien ne limite encore
    a_traiter = set(R)
    while a_traiter:
        s = max(a_traiter, key=lambda x: cap[x])    # extraction du MAXIMUM
        if cap[s] == 0:
            break
        a_traiter.remove(s)
        for v in R[s]:
            cap[v] = max(cap[v], min(cap[s], R[s][v]))   # relâchement min/max
    return cap

Justification-éclair, en miroir du théorème du cours : quand $s$ est extrait (le maximum des provisoires), tout autre chemin vers $s$ devrait sortir de la zone figée par un sommet $v$ de provisoire $\le \text{cap}[s]$, et son goulot final ne peut qu'être encore plus étroit (le $\min$ ne remonte jamais le long d'un chemin — l'analogue exact de « le reste du chemin pèse $\ge 0$ »). (La structure profonde de Dijkstra est là : une « addition » qui ne fait que dégrader le score le long d'un chemin, et une extraction par meilleur score — somme/min, min/max, produit de fiabilités/max (exercice 27 de la banque) : trois habillages du même théorème, et un exemple précoce de ce que « adapter un algorithme » veut dire — changer les opérateurs, re-vérifier l'invariant.)

def a_etoile_grille(p: int, q: int, depart: tuple, cible: tuple) -> tuple:
    """Grille p x q, pas de coût 1. Renvoie (distance, nb de sommets figés)."""
    def h(x):                                   # Manhattan : admissible ici
        return abs(x[0] - cible[0]) + abs(x[1] - cible[1])
    dist = {depart: 0}
    figes = set()
    candidats = {depart}
    while candidats:
        # priorité f = g + h ; à f égal, départager par h (le plus proche du but)
        s = min(candidats, key=lambda x: (dist[x] + h(x), h(x)))
        candidats.remove(s)
        figes.add(s)
        if s == cible:
            return (dist[s], len(figes))
        (i, j) = s
        for v in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= v[0] < p and 0 <= v[1] < q and v not in figes:
                if v not in dist or dist[s] + 1 < dist[v]:
                    dist[v] = dist[s] + 1
                    candidats.add(v)
    return (None, len(figes))

Résultats mesurés sur $100\times 100$ : distance $198$ pour les deux (la garantie d'admissibilité tient) ; sommets figés — Dijkstra (la même fonction avec $h=0$) : $10000$, soit toute la grille (le « disque » de rayon $198$ la couvre entièrement) ; A : $199$, une quasi-diagonale. Géométrie : Dijkstra fige par $g$ croissant — des cercles centrés au départ. Pour A, la grille vide est un cas extrême instructif : toute case y est sur un trajet parfait (en allant toujours vers le bas ou la droite, $g+h=198$ partout) — tous les candidats sont ex æquo, et c'est le départage par $h$ qui transforme cette indifférence en ligne droite vers la cible (sans lui, l'ordre des ex æquo est arbitraire et l'on fige la moitié de la grille : le tester !). Avec des obstacles, les cases des détours ont $f>198$ : A explore un fuseau autour des bons chemins, qui s'élargit juste ce qu'il faut pour contourner. (Facteur $50$ ici, davantage sur les grandes cartes : c'est l'écart entre « chercher partout » et « chercher là où ça peut être » — toute l'idée d'heuristique, chiffrée en une expérience de vingt lignes.)*

Avec $h^{\prime }=3\times$ Manhattan, la priorité $g+h^{\prime }$ écrase le terme $g$ : l'algorithme devient un fonceur quasi pur vers la cible (une « descente gloutonne », chapitre 7 !). Sur grille vide, aucun mal : le chemin direct est optimal. Le piège exige un détour payant dont l'entrée semble prometteuse. Configuration mesurée (grille $5\times 5$, départ $(0,0)$, cible $(4,4)$, murs sur $(1,0),(1,1),(2,4),(3,3)$) :

L'optimal (longueur $8$) bifurque tôt vers le bas, par la colonne $2$. Le fonceur, lui, longe la rangée du haut en réduisant $h^{\prime }$ à toute vitesse, plonge par la colonne $3$… et bute sur les murs $(3,3)$ et $(2,4)$ : il lui faut un crochet par $(2,2)$ — deux pas de détour. Revenir essayer la bifurcation manquée coûterait, à cause du facteur $3$, une priorité artificiellement énorme : il fige la cible sans l'avoir explorée et rend un chemin de longueur $10$ quand l'optimal vaut $8$ — en ayant figé moins de sommets que l'A admissible ($13$ contre $14$ : plus rapide, et faux). La preuve du cours montre où ça casse : « la cible figée a sa distance exacte » reposait sur le fait que tout candidat non figé porte $f\le$ vraie distance — vrai si $h$ ne surestime pas, faux sinon. Conclusion : l'admissibilité est le contrat qui sépare « plus rapide et toujours exact » (A admissible) de « encore plus rapide mais parfois faux » (heuristique gourmande) — le second a sa place (jeux temps réel), à condition d'être annoncé : c'est un choix de spécification, pas un détail. (Le triangle complet du semestre : Dijkstra prudent et prouvé, A guidé et prouvé, le fonceur véloce et faillible — trois points sur la frontière exactitude-vitesse, à choisir les yeux ouverts.)*

(a) La forme native : un Dijkstra depuis l'hôpital donne tout — « une source vers tous » en une exécution.

(b) Le piège des sens uniques : les distances vers un sommet ne sont pas celles depuis lui. Plutôt que $n$ exécutions (une par quartier — $O(n^3)$ !), retourner le graphe (chapitre 12, banque : inverser tous les arcs, $O(n+m)$) et lancer un seul Dijkstra depuis l'hôpital dans le graphe inverse : la distance de l'hôpital à $q$ dans l'inverse est exactement celle de $q$ à l'hôpital dans l'original — un changement de point de vue vaut $n-1$ exécutions.

(c) Un seul couple source-cible : Dijkstra avec arrêt dès que la cible est figée (licite : le théorème dit que sa distance est alors exacte — c'est l'arrêt qu'A pratique déjà), et si le graphe s'y prête, A avec une heuristique admissible pour concentrer l'exploration. En moyenne, l'arrêt anticipé fige environ la moitié des sommets, A bien moins ; le pire cas reste celui de Dijkstra complet — l'amélioration sans la garantie chiffrée, comme tous les arrêts anticipés du cours. (Trois variations sans une ligne d'algorithme nouveau : choisir la source, retourner le graphe, s'arrêter à temps — l'essentiel du métier consiste souvent à bien poser le problème devant un outil qu'on possède déjà ; et c'est la note finale juste pour un cours d'algorithmique : les théorèmes sont peu nombreux, leurs usages innombrables.)*