Algorithme de Chu-Liu/Edmonds

L'algorithme prend en entrée un graphe orienté ${\displaystyle G=\langle V,E\rangle }$ où ${\displaystyle V}$ est l'ensemble des sommets et ${\displaystyle E}$ est l'ensemble des arcs. Soit un sommet ${\displaystyle r}$ appelé la racine, et une valeur réelle de poids ${\displaystyle w(e)}$ pour chaque arc ${\displaystyle e\in E}$. L'algorithme renvoie une arborescence couvrante de poids minimal ${\displaystyle A}$ ancrée à la racine ${\displaystyle r}$, le poids d'une arborescence étant défini comme la somme des poids des arcs, ${\displaystyle w(A)=\sum _{e\in A}w(e)}$.

L'algorithme peut être exécuté de manière récursive. Soit ${\displaystyle f(G,r,w)}$ la fonction qui retourne une arborescence couvrante de poids minimal ancrée à la racine . On commence par supprimer tous les arcs de ${\displaystyle E}$ dont la destination est ${\displaystyle r}$. On remplace également tous les ensembles d'arcs parallèles (les arcs ayant la même origine et la même destination) par un seul arc avec un poids égal au poids minimal de l'ensemble associé.

Maintenant, pour chaque sommet ${\displaystyle v}$ autre que la racine, on prend l'arc de poids le plus faible dont la destination est ${\displaystyle v}$. On appelle l'origine de cet arc ${\displaystyle \pi (v)}$. Si l'ensemble d'arcs ${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus r\}}$ ne contient pas de cycles, alors ${\displaystyle f(G,r,w)=P}$.

Sinon, ${\displaystyle P}$ contient au moins un cycle. On choisit arbitrairement l'un de ces cycles. Soit ${\displaystyle C}$ ce cycle. Nous allons maintenant définir un nouveau graphe orienté et pondéré ${\displaystyle G'=\langle S',E'\rangle }$ dans lequel le cycle ${\displaystyle C}$ est "contracté" dans un seul sommet comme suit :

Les sommets de ${\displaystyle V'}$ sont les sommets de ${\displaystyle V\setminus C}$ plus un nouveau sommet dénoté ${\displaystyle v_{C}}$.

• Si ${\displaystyle (u,v)}$ est un arc de ${\displaystyle E}$ avec ${\displaystyle u\notin C}$ et ${\displaystyle v\in C}$ (un arc entrant dans le cycle), alors on inclut dans ${\displaystyle E^{\prime }}$ un nouvel arc ${\displaystyle e=(u,v_{C})}$, et on définit ${\displaystyle w^{\prime }(e)=w(u,v)-w(\pi (v),v)}$.
• Si ${\displaystyle (u,v)}$ est un arc de ${\displaystyle E}$ avec ${\displaystyle u\in C}$ et ${\displaystyle v\notin C}$ (un arc sortant du cycle), alors on inclut dans ${\displaystyle E^{\prime }}$ un nouvel arc ${\displaystyle e=(v_{C},v)}$, et on définit ${\displaystyle w^{\prime }(e)=w(u,v)}$.
• Si ${\displaystyle (u,v)}$ est un arc de ${\displaystyle E}$ avec ${\displaystyle u\notin C}$ et ${\displaystyle v\notin C}$ (un arc non-relié au cycle), alors on inclut dans ${\displaystyle E^{\prime }}$ un nouvel arc ${\displaystyle e=(u,v)}$, et on définit ${\displaystyle w^{\prime }(e)=w(u,v)}$.

Pour chaque arc de ${\displaystyle E'}$, on garde en mémoire l'arc de ${\displaystyle E}$ auquel il correspond.

Maintenant, on récupère une arborescence couvrante de poids minimal ${\displaystyle A^{\prime }}$ pour ${\displaystyle G'}$ en appelant ${\displaystyle f(G',r,w')}$. Comme ${\displaystyle A^{\prime }}$ est une arborescence couvrante, chacun de ses sommets a exactement un arc entrant. Soit ${\displaystyle (u,v_{C})}$ l'unique arc de ${\displaystyle A'}$ entrant dans ${\displaystyle v_{C}}$. Cet arc correspond à un arc ${\displaystyle (u,v)\in E}$ avec ${\displaystyle v\in C}$. On supprime ${\displaystyle (\pi (v),v)}$de ${\displaystyle C}$, pour briser le cycle. On garde tous les autres arcs de ${\displaystyle C}$. Pour chaque arc dans ${\displaystyle A^{\prime }}$, on garde son arc correspondant dans ${\displaystyle E}$. Maintenant, ${\displaystyle f(G,r,w)}$ est défini par les arcs que nous avons gardés, qui forment une arborescence couvrante de poids minimal.On note que ${\displaystyle f(G,r,w)}$ est défini à l'aide de ${\displaystyle f(G',r,w')}$, avec ${\displaystyle G'}$ ayant strictement moins de sommets que ${\displaystyle G}$. Trouver ${\displaystyle f(G,r,w)}$ pour un graphe contenant un seul sommet est trivial (il s'agit de ${\displaystyle G}$ lui-même), ainsi la terminaison de l'algorithme est garantie.