Algorithme de Johnson : plus courts chemins toutes paires

L'algorithme de Johnson (1977) calcule les plus courts chemins entre toutes les paires de sommets d'un graphe pondéré, y compris avec des poids négatifs (mais sans cycle négatif). Il combine Bellman-Ford et Dijkstra via une astuce de repondération.

Idée clé : la repondération

Dijkstra ne fonctionne pas avec des poids négatifs. L'idée de Johnson est de transformer les poids pour les rendre tous positifs, sans changer les plus courts chemins.

On ajoute un sommet fictif $s$ relié à tous les sommets par des arêtes de poids 0. On exécute Bellman-Ford depuis $s$ pour obtenir une fonction de potentiel $h(v)$.

Nouveau poids : $\hat{w}(u,v) = w(u,v) + h(u) - h(v) \geq 0$. Les plus courts chemins sont préservés car $h(u) - h(v)$ est un terme télescopique.

Algorithme complet

• Ajouter un sommet fictif $s$ avec des arêtes $(s, v, 0)$ pour tout $v$.
• Exécuter Bellman-Ford depuis $s$ → obtenir $h(v)$ pour chaque sommet.
• Si un cycle négatif est détecté : arrêter (pas de solution).
• Repondérer : $\hat{w}(u,v) = w(u,v) + h(u) - h(v)$.
• Pour chaque sommet $u$ : exécuter Dijkstra depuis $u$ avec les poids $\hat{w}$.
• Corriger les distances : $d(u,v) = \hat{d}(u,v) - h(u) + h(v)$.

Complexité

Bellman-Ford : $O(VE)$. Puis $V$ appels à Dijkstra : $O(V(V \log V + E))$ avec un tas de Fibonacci.

Total : $O(V^2 \log V + VE)$. C'est meilleur que Floyd-Warshall ($O(V^3)$) pour les graphes creux ($E \ll V^2$).

Quand l'utiliser ?

• Graphe creux + poids négatifs → Johnson.
• Graphe dense → Floyd-Warshall (plus simple, mêmes performances).
• Pas de poids négatifs → $V$ appels à Dijkstra directement.

Une question ou une suggestion ? Écrivez-nous.