Poids négatifs : ajouter une constante ne sauve rien

Non, et il faut comprendre pourquoi, car l'idée revient souvent.

Les vraies distances, calculées par un algorithme qui supporte les poids négatifs : $[0;1;5;2]$. Dijkstra rend $[0;1;5;3]$ — juste partout sauf en $3$, où il rend $3$ au lieu de $2$.

Après le décalage $p\mapsto p+4$, tous les poids sont positifs et Dijkstra est applicable. Il rend $[0;6;9;11]$. Retranchons le décalage : le chemin retenu vers $3$ est $0\to 1\to 3$, de coût décalé $6+5=11$, soit $11-2\times 4=3$ dans le graphe d'origine. Toujours faux.

La raison, et elle est structurelle. Le décalage n'ajoute pas la même chose à tous les chemins : il ajoute $4$ par arc. Comparons les deux chemins de $0$ à $3$ :

Le chemin optimal a trois arcs, l'autre en a deux : le décalage pénalise le premier de $12$ et le second de $8$. Il inverse donc l'ordre. Le décalage préserve l'ordre des chemins de même longueur en nombre d'arcs, et lui seul — ce qui ne sert à rien, puisque c'est justement entre chemins de longueurs différentes qu'il faut trancher.

Ce qui marche, et ce n'est pas un décalage constant. Il existe un repondérage correct, dû à Johnson : on choisit un potentiel $h(v)$ par sommet et l'on remplace $p(u,v)$ par $p(u,v)+h(u)-h(v)$. Les termes se télescopent le long d'un chemin de $s$ à $t$ : le coût devient $\text{couˆt reˊel}+h(s)-h(t)$, le même décalage pour tous les chemins de $s$ à $t$, quelle que soit leur longueur. L'ordre est donc préservé. Il reste à trouver $h$ tel que les nouveaux poids soient positifs — et l'on prend $h(v)=$ distance depuis un sommet fictif relié à tous, calculée par... un algorithme supportant les poids négatifs. Le problème suivant en donne un.