Algorithme de Johnson

Carte Commune · n° 480154

En informatique, l'algorithme de Johnson calcule des plus courts chemins entre toutes les paires de sommets dans un graphe orienté, aux arcs pondérés. Les poids des arcs peuvent être des nombres négatifs pourvu qu'il n'existe pas de circuits de poids négatif. Il est particulièrement efficace lorsque le graphe est creux. L'algorithme opère en utilisant d'abord l'algorithme de Bellman-Ford pour calculer une transformation du graphe de départ qui supprime tous les poids négatifs, ce qui permet l'emploi, dans un deuxième temps, de l’algorithme de Dijkstra sur le graphe transformé. L'algorithme est nommé d'après Donald B. Johnson (en) qui le premier a publié cette méthode en 1977. Une technique similaire de repondération est aussi utilisée dans l'algorithme de Suurballe (en) pour la recherche de deux chemins disjoints de longueur totale minimale entre deux même sommets dans un graphe pondéré positivement.

Lire sur Wikipédia