Voir la source de Algorithme de Johnson

{{Infobox Algorithme}}

{{Voir homonyme|texte=Un algorithme de même nom est mentionné dans {{Lien|Job Shop Scheduling}}}}

En [[informatique]], l{{'}}'''algorithme de Johnson''' calcule des [[Problèmes de cheminement|plus courts chemins]] entre [[Problèmes de cheminement|toutes les paires de sommets]] dans un [[graphe orienté]], aux arcs [[Lexique de la théorie des graphes#P|pondérés]]. Les poids des arcs peuvent être des [[nombre négatif|nombres négatifs]] pourvu qu'il n'existe pas de [[Circuit (graphe)|circuits]] de poids négatif. Il est particulièrement efficace lorsque le graphe est [[Graphe dense|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é<ref name="clrs">Section 25.3,  « Algorithme de Johnson pour les graphes peu denses », {{p.|616-620}} dans :  {{Cormen2fr}}</ref>{{,}}<ref name="black">{{chapitre | titre=Johnson's Algorithm | prénom=Paul E.|nom=Black|titre ouvrage=Dictionary of Algorithms and Data Structures|éditeur=[[National Institute of Standards and Technology]]| url=http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html | année=2004 }}.</ref>. 
L'algorithme est nommé d'après {{Lien|fr=Donald B. Johnson|lang=en|trad=Donald B. Johnson|texte=Donald B. Johnson}} qui le premier a publié cette méthode en 1977<ref>{{article|prénom=Donald B.|nom=Johnson|lien auteur=Donald B. Johnson|titre=Efficient algorithms for shortest paths in sparse networks|journal=[[Journal of the ACM]]|volume=24|numéro=1|pages=1–13|année=1977|doi=10.1145/321992.321993}}.</ref>.

Une technique similaire de '''repondération''' est aussi utilisée dans l'{{Lien|fr=algorithme de Suurballe|lang=en|trad=Suurballe's algorithm}} pour la recherche de deux chemins disjoints de longueur totale minimale entre deux même sommets dans un graphe pondéré positivement<ref>{{article|prénom=J. W.|nom=Suurballe|titre=Disjoint paths in a network|journal=Networks|volume=14|pages=125–145|année=1974|doi=10.1002/net.3230040204|numéro=2}}.</ref>.

==Description de l'algorithme==
L'algorithme est composé des étapes suivantes{{refm|"clrs"|"black"}} :
#Ajouter un nouveau sommet {{math|''q''}} au graphe, et  connecter ce sommet par des [[graphe (mathématiques discrètes)|arcs]] de poids nul à tous les autres nœuds.
#Utiliser l'[[algorithme de Bellman-Ford]] en partant du nouveau sommet {{math|''q''}} pour déterminer, pour chaque sommet  {{math|''v''}}, le poids minimum {{math|''h''(''v'')}} d'un chemin de {{math|''q''}} à {{math|''v''}}. Si on détecte un cycle négatif, l'algorithme s'arrête sur un échec.
#''Repondérer'' les arcs du graphe initial en utilisant les valeurs calculées par l'algorithme de Bellman-Ford : un arc de {{math|''u''}} à {{math|''v''}}, dont l’ancien poids est le nombre  {{math|''w(u,v)''}}, a pour nouveau poids le nombre positif {{math|''w(u,v)'' + ''h(u)'' &minus; ''h(v)''}}.
#Enlever le sommet  {{math|''q''}} et, pour tout sommet s, appliquer l'[[algorithme de Dijkstra]] depuis la source s (on peut alors déterminer des plus courts chemins de tout sommet à tout sommet dans le graphe aux nouveaux poids). 

== Exemple ==

{| 
|valign = top |[[Fichier:Algorithme de johnson 1.svg|vignette|Graphe initial]] 
|valign = top| [[Fichier:Algorithme de johnson2.svg|vignette|Ajout d'un nouveau sommet source, noté {{math|''q''}}]]
|valign = top|[[Fichier:Algorithme de johnson 3.svg|vignette|Arbre couvrant des plus courts chemins produit par l'algorithme de Bellman-Ford depuis le sommet source {{math|''q''}}]]
|valign = top|[[File:Algorithme de johnson étape 4.jpg|thumb|Graphe repondéré positivement où on applique l'algorithme de Dijkstra en prenant chaque sommet un à un comme sommet source]]
|}

Le graphe initial (à gauche dans l'illustration) possède deux arcs négatifs, mais pas de cycle négatif. On représente ensuite le graphe avec un nouveau sommet {{math|''q''}} et des arcs de poids nuls vers tous les sommets du graphe initial x, y, z et w. Puis, on montre un arbre des plus courts chemins calculé par l'algorithme de Bellman-Ford avec {{math|''q''}} comme sommet source. Les valeurs {{math|''h''(''v'')}} (en orange dans le dessin) affectées à chaque nœud sont les poids des plus courts chemins de {{math|''q''}} vers ce nœud. Ces valeurs sont toutes négatives ou nulles, puisque par construction {{math|''q''}} a déjà un arc de poids nul vers chaque sommet et un plus court chemin ne peut être pas plus lourd que cet arc. Sur la droite est représenté le graphe repondéré. Il est formé en remplaçant chaque poids d'arc {{math|''poids(u,v)''}} par {{math|''poids(u,v)'' + ''h(u)'' &minus; ''h(v)''}}. Dans ce graphe repondéré, les poids des arcs sont toujours positifs ou nuls, et un plus court chemin entre deux sommets arbitraires utilise la même séquence d'arcs qu'un plus court chemin entre ces deux mêmes sommets dans le graphe initial. L'algorithme se termine en appliquant plusieurs fois l'algorithme de Dijkstra pour chacun des quatre sommets de départ dans le graphe repondéré.

==Correction de l'algorithme==

=== La repondération est réversible ===
Dans le graphe repondéré, tout chemin d'un nœud <math>s</math> à un nœud <math>t</math> est augmenté de la même valeur <math>h(s)-h(t)</math>.

{{boîte déroulante/début|titre=Démonstration}}
En effet, soit <math>c=(s, p_1,p_2,\ldots,p_n,t)</math> un chemin de <math>s</math> à <math>t</math>. Son poids dans le graphe repondéré est :

:<math>\bigl(poids(s, p_1) + h(s) - h(p_1)\bigr) + \bigl(poids(p_1, p_2) + h(p_1) - h(p_2)\bigr) + ... + \bigl(poids(p_n, t) + h(p_n) - h(t)\bigr).</math>

Chaque terme <math>+h(p_i)</math> est annulé par le terme <math>-h(p_i)</math> dans l'expression précédente entre parenthèses. C'est une [[somme télescopique]]. On obtient donc :

:<math>\bigl(poids(s, p_1) + poids(p_1, p_2) + ... + poids(p_n, t)\bigr)+ h(s) - h(t)</math>.

L'expression entre parenthèses est le poids du chemin dans la pondération initiale. La repondération augmente donc de la même valeur <math>h(s)-h(t)</math> chaque chemin de <math>s</math> à <math>t</math>.
{{boîte déroulante/fin}}
En particulier, un chemin de <math>s</math> à <math>t</math> est un plus court chemin avec les poids de départ si et seulement s'il est un plus court chemin avec la nouvelle pondération. Ainsi, si on calcule des plus courts chemins dans le graphe repondéré, on obtient des plus courts chemins en inversant la transformation de repondération<ref name="clrs" />. 

=== Le graphe repondéré est positif ===
D'autre part, tous les arcs du graphe repondéré sont de poids positifs.

{{boîte déroulante/début|titre=Démonstration}}
Remarquons que le poids d'un plus court chemin de q à tout autre sommet u est nulle dans le graphe repondéré. En effet, un tel plus court chemin est aussi un plus court chemin dans le graphe initial où on a ajouté q. Et par définition de la repondération, le poids repondéré de chaque arc d'un tel plus court chemin est nulle.
Ainsi, dans le graphe repondéré, pour tout arc (u, v), le poids du chemin q → u → v est 0 + poids(u, v). Il est supérieur à 0 car le poids d'un plus court chemin de q à v est 0. Donc l'arc (u, v) est de poids positif.
{{boîte déroulante/fin}}

Comme les arcs sont tous de poids positifs dans le graphe repondéré, les exécutions de l'algorithme de Dijkstra sont correctes.

== Pseudo-code ==
 Entrée : G un graphe pondéré sans cycle de poids négatif
 Sortie : les distances entre toutes paires de sommets
 
 Johnson(G)
           G1 := G où on a ajouté un sommet q et des arcs entre q et tout sommet de G
           h[.] := {{Souligner|Bellman-Ford}}(G1, q)
           G2 := G où pour chaque arc (s, t), le poids de (s, t) est poids(s, t) + h(s) - h(t) où poids(s, t) est le poids de (s, t) dans G
           '''pour tout''' sommet s de G
                     d[s, .] := {{Souligner|Dijkstra}}(G, s)
           '''pour tout''' s, t sommets de G
                     d[s, t] := d[s, t] - (  h(s) - h(t) )
           '''retourner''' d

==Analyse de complexité==
La [[complexité en temps]] de cet algorithme est, en utilisant un [[tas de Fibonacci]] pour l’implémentation de l'algorithme de Dijkstra, en <math>O (|V|^2 \log |V| + |V||E|)</math>. L'algorithme  prend en effet un temps  <math>O (|V||E|)</math>  pour la phase composée de l'algorithme de Bellman-Ford, et <math>O (|V| \log |V|)</math> pour chacun des {{math|{{!}}''V''{{!}}}} appels de l'algorithme de Dijkstra. Ainsi, lorsque le graphe est creux, le temps total peut être inférieur à celui de l'[[algorithme de Floyd-Warshall]] qui résout le même problème en temps <math>O (|V|^3)</math><ref name="clrs"/>.

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|Johnson's algorithm| 564595231|type=note}}
== Liens externes ==
*[http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/johnson_all_pairs_shortest.html Boost: All Pairs Shortest Paths]. Un programme en C++

{{Palette|Algorithmes sur les graphes}}
{{Portail|Informatique théorique}}
[[Catégorie:Algorithme de la théorie des graphes|Johnson]]