Arbre couvrant de poids minimal

Un premier essai

Il peut être très simple de créer un algorithme qui découvrira un arbre à portée minimale :

 fonction MST(G,W) :      T = {     } alors que T ne forme pas un arbre de couverture :          trouver le bord minimum pondéré dans E qui est sûr pour l'union T T = T {(u,v)}      renvoie T

Dans ce cas, "sûr" signifie que l'inclusion du bord ne forme pas un cycle dans le graphique. Un cycle signifie que l'on part d'un sommet, que l'on se rend à plusieurs autres sommets et que l'on se retrouve au point de départ sans utiliser deux fois la même arête.

Histoire

Le scientifique tchèque Otakar Borůvka a développé le premier algorithme connu pour trouver un arbre à portée minimale, en 1926. Il voulait résoudre le problème de la couverture efficace de la Moravie par l'électricité. Aujourd'hui, cet algorithme est connu sous le nom d'algorithme de Borůvka. Deux autres algorithmes sont couramment utilisés aujourd'hui. L'un d'eux a été développé par Vojtěch Jarník en 1930, et mis en pratique par Robert Clay Prim en 1957. Edsger Wybe Dijkstra l'a redécouvert en 1959, et l'a appelé l'algorithme de Prim. L'autre algorithme est appelé algorithme de Kruskal, et a été pulbisé par Joseph Kruskal en 1956. Les trois algorithmes sont gourmands et fonctionnent en temps polynomial.

L'algorithme de l'arbre à portée minimale le plus rapide à ce jour a été développé par Bernard Chazelle. L'algorithme est basé sur le soft heap, une file d'attente de priorité approximative. Son temps de fonctionnement est O(m α(m,n)), où m est le nombre d'arêtes, n le nombre de sommets et α est l'inverse fonctionnel classique de la fonction d'Ackermann. La fonction α croît extrêmement lentement, de sorte qu'à toutes fins pratiques, elle peut être considérée comme une constante ne dépassant pas 4 ; l'algorithme de Chazelle prend donc un temps très proche du temps linéaire.

Quel est l'algorithme le plus rapide possible pour ce problème ? C'est l'une des plus anciennes questions ouvertes en informatique. Il y a clairement une limite inférieure linéaire, puisque nous devons au moins examiner tous les poids. Si les poids de bord sont des entiers avec une longueur de bit limitée, alors les algorithmes déterministes sont connus avec un temps de fonctionnement linéaire. Pour les poids généraux, il existe des algorithmes randomisés dont le temps de fonctionnement prévu est linéaire.

Le problème peut également être abordé de manière distribuée. Si chaque nœud est considéré comme un ordinateur et qu'aucun nœud ne sait rien d'autre que ses propres liens connectés, on peut toujours calculer l'arbre de couverture minimum distribué.