Prérequis

Afin de comprendre le fonctionnement de l’algorithme de Johnson, il est nécessaire de connaître deux autres algorithmes de plus court chemin :

1. Algorithme de Dijkstra - Exemple
2. Algorithme de Bellman-Ford - Exemple

Idée de l’algorithme

1. Ajout d’un sommet : Nous ajoutons un sommet $w$ au graphe $G$ ainsi que $|V|$ arrêtes reliant $w$ à chaque sommet de $G$.
2. Nous utilisons l’algorithme de Bellman-Ford depuis $w$ vers tous les autres sommets de $G$. $d(s)$ nous donne la distance entre $w$ et $s$ Si Bellman-Ford détecte un cycle absorbant, l’algorithme s’arrête.
3. Suppression du sommet $w$ : Ce sommet n’est désormait plus utile. Supprimez ce sommet ainsi que toutes les arrêtes ajoutées à l’étape 1.
4. Repondérons les arcs du graphe : Pour chaque arrête $(u,v)$ du graphe, faire : $p((u,v)) := p((u,v)) + d(u) - d(v)$.
5. Calcul du plus court chemin. Pour chaque sommet de $G$, appliquez l’algorithme de Dijkstra afin de déterminer le plus court chemin entre tous les sommets.

Il faut bien prendre en compte que les distances ne sont pas conservées. Si pour un arcs, nous avions un poids de $-2$, le nouveau poids sera $\geq 0$. Cependant, ce n’est pas le propos. L’algorithme de Johnson nous donne le plus court chemin d’un points $A$ à un points $B$ “uniquement”. Si vous avez besoin de récupérer la somme des poids de ce chemin, il suffit de retourner dans le graphe initial et de suivre le chemin donnée par Johnson.

Algorithme / Correction / Complexité

Cet article présente seulement un exemple d’application de l’algorithme de Johnson. Vous pouvez cependant facilement trouver ces informations sur internet :

• https://stringfixer.com/fr/Johnson%27s_algorithm
• https://www.wikiwand.com/fr/Algorithme_de_Johnson

Exemple :

Soit $G$ un graphe avec des arcs de poids négatif.

Graphe Initial

Etape 1 - Ajout du sommet w

Ajout de w

Etape 2 - Plus courts chemins entre w et les autres sommets avec Bellman-Ford

Plus courts chemins ajoutés

En violet les résultats de l’algorithmes de Bellman-Ford.

Etape 3 et 4 - Repondération des arcs

Repondération des arcs

Etape 5 - Algorithme de Dijkstra sur tout les arcs

Nous avons au final le graphe $G’$ suivant :

Graphe G'

L’étape 5 est uniquement une application de l’algorithme de Dijkstra. Un exemple d’utilisation est déja détaillé sur ce site : Algorithme de Dijkstra - Exemple.

Pour prendre plusieurs résultats de l’algorithme de Dijkstra :

• Pour aller de a à d, le chemin à prendre est $a \rightarrow b \rightarrow c \rightarrow d$ de poids -9 (et non 0, il faut prendre les poids de $G$ et pas de $G’$).
• Pour aller de f à d, le chemin à prendre est $f\rightarrow e \rightarrow c \rightarrow d$ de poids -2.
• Pour aller de d à e, il n’existe pas de chemin possible.

Le reste sera laissé en exercice pour le lecteur.