Algorithme de Johnson

Découvreur ou inventeur	Donald B. Johnson (en)
Date de publication	1977
Problèmes liés	Algorithme, algorithme de la théorie des graphes (en), problèmes de cheminement
Structure des données	Graphe

Complexité en temps

Pire cas	${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$

modifier - modifier le code - modifier Wikidata

Un algorithme de même nom est mentionné dans Job Shop Scheduling (en)

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].

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].

L'algorithme est composé des étapes suivantes^[1],[2] :

1. Ajouter un nouveau sommet q au graphe, et connecter ce sommet par des arcs de poids nul à tous les autres nœuds.
2. Utiliser l'algorithme de Bellman-Ford en partant du nouveau sommet q pour déterminer, pour chaque sommet v, le poids minimum h(v) d'un chemin de q à v. Si on détecte un cycle négatif, l'algorithme s'arrête sur un échec.
3. Repondérer les arcs du graphe initial en utilisant les valeurs calculées par l'algorithme de Bellman-Ford : un arc de u à v, dont l’ancien poids est le nombre w(u,v), a pour nouveau poids le nombre positif w(u,v) + h(u) − h(v).
4. Enlever le sommet 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).

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 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 q comme sommet source. Les valeurs h(v) (en orange dans le dessin) affectées à chaque nœud sont les poids des plus courts chemins de q vers ce nœud. Ces valeurs sont toutes négatives ou nulles, puisque par construction 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 poids(u,v) par poids(u,v) + h(u) − 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é.

Dans le graphe repondéré, tout chemin d'un nœud ${\displaystyle s}$ à un nœud ${\displaystyle t}$ est augmenté de la même valeur ${\displaystyle h(s)-h(t)}$.

En particulier, un chemin de ${\displaystyle s}$ à ${\displaystyle t}$ 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^[1].

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

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

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[.] := 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, .] := Dijkstra(G, s)
          pour tout s, t sommets de G
                    d[s, t] := d[s, t] - (  h(s) - h(t) )
          retourner d

La complexité en temps de cet algorithme est, en utilisant un tas de Fibonacci pour l’implémentation de l'algorithme de Dijkstra, en ${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$. L'algorithme prend en effet un temps ${\displaystyle O(|V||E|)}$ pour la phase composée de l'algorithme de Bellman-Ford, et ${\displaystyle O(|V|\log |V|)}$ pour chacun des |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 ${\displaystyle O(|V|^{3})}$^[1].

• Boost: All Pairs Shortest Paths. Un programme en C++

• Portail de l'informatique théorique