Algorithme de Johnson

En informatique, lModèle:'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éModèle:,. L'algorithme est nommé d'après Modèle:Lien qui le premier a publié cette méthode en 1977.

Une technique similaire de repondération est aussi utilisée dans l'Modèle:Lien pour la recherche de deux chemins disjoints de longueur totale minimale entre deux même sommets dans un graphe pondéré positivement.

Description de l'algorithme

L'algorithme est composé des étapes suivantesModèle:Refm :

1. Ajouter un nouveau sommet Modèle:Math 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 Modèle:Math pour déterminer, pour chaque sommet Modèle:Math, le poids minimum Modèle:Math d'un chemin de Modèle:Math à Modèle:Math. 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 Modèle:Math à Modèle:Math, dont l’ancien poids est le nombre Modèle:Math, a pour nouveau poids le nombre positif Modèle:Math.
4. Enlever le sommet Modèle:Math 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

Graphe initial

Ajout d'un nouveau sommet source, noté Modèle:Math

Arbre couvrant des plus courts chemins produit par l'algorithme de Bellman-Ford depuis le sommet source Modèle:Math

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 Modèle:Math 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 Modèle:Math comme sommet source. Les valeurs Modèle:Math (en orange dans le dessin) affectées à chaque nœud sont les poids des plus courts chemins de Modèle:Math vers ce nœud. Ces valeurs sont toutes négatives ou nulles, puisque par construction Modèle:Math 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 Modèle:Math par Modèle:Math. 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 $s$ à un nœud $t$ est augmenté de la même valeur $h(s)-h(t)$.

Modèle:Boîte déroulante/début En effet, soit $c=(s,p_1,p_2,\dots ,p_n,t)$ un chemin de $s$ à $t$. Son poids dans le graphe repondéré est :

$(poids(s,p_1)+h(s)-h(p_1))+(poids(p_1,p_2)+h(p_1)-h(p_2))+...+(poids(p_n,t)+h(p_n)-h(t)).$

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

$(poids(s,p_1)+poids(p_1,p_2)+...+poids(p_n,t))+h(s)-h(t)$.

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 $h(s)-h(t)$ chaque chemin de $s$ à $t$. Modèle:Boîte déroulante/fin En particulier, un chemin de $s$ à $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.

Le graphe repondéré est positif

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

Modèle:Boîte déroulante/début 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. Modèle: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[.] := Modèle:Souligner(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, .] := Modèle:Souligner(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 $O(|V{|}^2\log |V|+|V||E|)$. L'algorithme prend en effet un temps $O(|V||E|)$ pour la phase composée de l'algorithme de Bellman-Ford, et $O(|V|\log |V|)$ pour chacun des Modèle:Math 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 $O(|V{|}^3)$.

Liens externes

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