Algorithme de Johnson
De Wikipedia, l'encyclopédie encyclopedia
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é[1],[2]. L'algorithme est nommé d'après Donald B. Johnson (en) qui le premier a publié cette méthode en 1977[3].
Découvreur ou inventeur |
Donald B. Johnson (en) |
---|---|
Date de publication | |
Problèmes liés |
Algorithme, algorithme de la théorie des graphes (d), problèmes de cheminement |
Structure des données |
Pire cas |
---|
Un algorithme de même nom est mentionné dans Job Shop Scheduling (en)
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[4].