Un graphe se compose de sommets et d’arêtes. Chaque arête de notre exemple possède un poids positif, ou coût : il peut représenter une distance, une durée ou une énergie. Nous utilisons des graphes non orientés et connexes : chaque sommet est accessible depuis les autres.
Un même réseau pose des questions différentes. Dijkstra cherche les chemins les moins coûteux depuis un sommet de départ. Prim et Kruskal cherchent plutôt un arbre reliant tous les sommets sans cycle et avec la plus petite somme des poids. Un plus court chemin et un arbre couvrant minimal ne sont pas le même objet.
Un petit exemple commun
Considérons quatre sommets A, B, C, D et les arêtes A–B de poids 4, A–C de poids 2, B–C de poids 1, B–D de poids 5 et C–D de poids 8. De A à D, le chemin A–C–B–D coûte 2+1+5=8 ; A–B–D coûte 9 et A–C–D coûte 10. Un arbre minimal choisit B–C, A–C et B–D, pour un poids total de 1+2+5=8. Cette égalité de valeur est fortuite : le premier problème mesure un seul trajet, le second un réseau qui relie tout le monde.
1. Dijkstra : fixer des distances de plus en plus sûres
On donne la distance 0 au départ et une distance provisoire infinie aux autres sommets. À chaque étape, on choisit le sommet non encore fixé dont la distance provisoire est minimale. On tente ensuite de réduire les distances de ses voisins en ajoutant le poids de chaque arête. Avec des poids non négatifs, la distance choisie est définitive. Dans le petit exemple, depuis A on découvre C au coût 2 et B au coût 4 ; par C on améliore B à 3 ; par B on atteint D au coût 8.
Limite importante : ce raisonnement ne fonctionne pas en général avec des poids négatifs.
2. Prim : faire grandir un arbre
On choisit un sommet de départ. À chaque étape, on prend l’arête la moins lourde qui relie un sommet déjà dans l’arbre à un sommet extérieur. Le groupe connecté grandit sans former de cycle, jusqu’à englober tous les sommets. Prim regarde toujours la frontière de l’arbre en cours : son choix dépend du réseau déjà construit.
3. Kruskal : trier les arêtes et éviter les cycles
On trie toutes les arêtes de la plus légère à la plus lourde. On accepte une arête si elle relie deux groupes jusque-là distincts ; on la rejette si elle fermerait un cycle. Les groupes fusionnent peu à peu en un seul arbre. Prim et Kruskal peuvent choisir des arêtes différentes en cas d’égalité, mais le poids total minimal coïncide.
Essayer le même graphe
Dans le laboratoire interactif des graphes pondérés, créez un graphe aléatoire connexe de 20 à 100 sommets avec des poids entiers de 1 à 20. La graine permet de reproduire le même graphe ; choisissez départ et arrivée pour Dijkstra, puis comparez Prim et Kruskal sur ce même réseau. Avancez étape par étape ou lancez l’animation. Les positions facilitent la lecture, mais la longueur dessinée d’une arête ne représente pas son poids.
Que comparer ?
Pour Dijkstra, observez comment une distance provisoire diminue avant de devenir définitive. Pour Prim et Kruskal, comparez le poids total final : il doit coïncider même si l’ordre des choix diffère. Sur un grand graphe, masquez les poids pour mieux voir la structure ; celui de l’arête examinée reste visible.