Trois objectifs distincts : moins de déplacements, un trajet moins coûteux, ou relier tous les points au moindre coût total. Un même graphe permet de comprendre la différence.
Un graphe comprend des sommets V et des arêtes E. Celui-ci est simple, non orienté et connexe, avec 6 sommets et 9 arêtes. Chaque liaison se parcourt dans les deux sens. Les nombres sont des coûts, pas les longueurs du dessin. Les voisins sont traités par ordre alphabétique ; les égalités de poids sont départagées par le nom des arêtes. Un chemin relie des sommets, un cycle revient au départ sans répéter les autres sommets. Un arbre est connexe et sans cycle.
A–B: 4 A–C: 2 B–C: 1 B–D: 5 C–D: 8 C–E: 10 D–E: 2 D–F: 6 E–F: 3
Traits verts continus : arêtes choisies ou prédécesseurs actuels ; gris pointillés : autres arêtes. BFS omet les poids. Les prédécesseurs intermédiaires de Dijkstra peuvent changer. ∞ indique une distance encore inconnue.
1. BFS : le moins de déplacements
Le parcours en largeur ignore les poids : chaque arête vaut un déplacement. Depuis A, nous cherchons le nombre minimal d’arêtes vers chaque sommet accessible. La file FIFO retire le premier élément entré.
Fixer d(A)=0 et placer A dans la file. Retirer u en tête ; pour chaque voisin v non découvert, fixer d(v)=d(u)+1, mémoriser u comme prédécesseur et ajouter v. Marquer v dès son insertion pour éviter les doublons. Continuer jusqu’à vider la file.
| Étape | Sommet / arête | File / ensemble définitif / coût | Distances dans l’ordre A, B, C, D, E, F |
|---|---|---|---|
| 0 | — | [A] | 0, ∞, ∞, ∞, ∞, ∞ |
| 1 | A | [B, C] | 0, 1, 1, ∞, ∞, ∞ |
| 2 | B | [C, D] | 0, 1, 1, 2, ∞, ∞ |
| 3 | C | [D, E] | 0, 1, 1, 2, 2, ∞ |
| 4 | D | [E, F] | 0, 1, 1, 2, 2, 3 |
| 5 | E | [F] | 0, 1, 1, 2, 2, 3 |
| 6 | F | [] | 0, 1, 1, 2, 2, 3 |
Après A : [B,C]. B découvre D ; C découvre E sans modifier D. D découvre F. A–B–D–F utilise 3 arêtes, comme A–C–E–F : plusieurs solutions sont possibles. Le premier chemin coûte 15 ; moins de déplacements ne signifie donc pas moins cher.
Pourquoi cela fonctionne
- Invariant : les distances dans la file sont croissantes au sens large. Pendant le traitement du niveau k, les nouveaux sommets sont ajoutés au niveau k+1 en fin de file.
- Initialisation : A est correctement au niveau 0. Supposons correctes les distances jusqu’au niveau k. Tout nouveau voisin d’un sommet de niveau k est accessible en k+1 arêtes.
- Il ne peut exister de chemin plus court : son prédécesseur sur ce chemin aurait été traité à un niveau antérieur et l’aurait déjà découvert. La première distance attribuée est donc minimale. Les prédécesseurs reconstruisent un plus court chemin.
Avec des listes d’adjacence : chaque sommet est ajouté une fois, chaque arête examinée deux fois. Temps O(|V|+|E|), mémoire auxiliaire O(|V|), hors graphe. Si le graphe est non connexe, seule la composante de A est visitée.
Princeton · Algorithms, 4th Edition — BFS
2. Dijkstra : le chemin de coût minimal
Les poids comptent et doivent être non négatifs. d(v) est le meilleur coût trouvé, initialement infini sauf d(A)=0. S contient les sommets dont la distance est définitive.
Choisir hors de S le sommet u de plus petit d(u), puis l’ajouter à S. Pour tout voisin v hors de S, effectuer la relaxation d(v) ← min(d(v), d(u)+w(u,v)). Modifier le prédécesseur en cas d’amélioration. Si le minimum est infini, les sommets restants sont inaccessibles.
| Étape | Sommet / arête | File / ensemble définitif / coût | Distances dans l’ordre A, B, C, D, E, F |
|---|---|---|---|
| 0 | — | {} | 0, ∞, ∞, ∞, ∞, ∞ |
| 1 | A | {A} | 0, 4, 2, ∞, ∞, ∞ |
| 2 | C | {A, C} | 0, 3, 2, 10, 12, ∞ |
| 3 | B | {A, C, B} | 0, 3, 2, 8, 12, ∞ |
| 4 | D | {A, C, B, D} | 0, 3, 2, 8, 10, 14 |
| 5 | E | {A, C, B, D, E} | 0, 3, 2, 8, 10, 13 |
| 6 | F | {A, C, B, D, E, F} | 0, 3, 2, 8, 10, 13 |
Après A : B=4, C=2. C améliore B à 3, propose D=10 et E=12. B améliore D à 8. D améliore E à 10 et propose F=14. E améliore F à 13. A–C–B–D–E–F coûte 2+1+5+2+3=13, mais utilise 5 arêtes, davantage que BFS.
Pourquoi cela fonctionne
- Chaque estimation finie correspond à un chemin réel : elle ne sous-estime pas l’optimum. Supposons correctes les distances déjà fixées dans S.
- Si u avait un chemin moins coûteux, soit y le premier sommet de ce chemin hors de S et x son prédécesseur dans S. La relaxation depuis x a donné à y une estimation au plus égale au coût de ce préfixe.
- Les poids restants sont non négatifs : le préfixe ne coûte pas plus que le chemin entier vers u. Ainsi d(y) serait inférieur à d(u), contradiction avec le choix du minimum. La distance fixée est correcte ; on conclut par récurrence.
Listes d’adjacence et tas binaire avec diminution de clé : O((|V|+|E|) log |V|), mémoire auxiliaire O(|V|). Une recherche du minimum par balayage coûte O(|V|²+|E|). Des poids négatifs invalident la preuve : pour A→B=2, A→C=5, C→B=−10, B serait fixé à 2 alors que le minimum est −5.
Princeton · Algorithms, 4th Edition — Dijkstra
3. Kruskal : tout relier au moindre coût
Nous cherchons un réseau reliant tous les sommets avec une somme des poids minimale, et non un trajet de A à F. C’est un arbre couvrant minimal (MST). Un arbre de 6 sommets a exactement 5 arêtes.
Trier les arêtes par poids croissant. Initialement chaque sommet forme une composante. Accepter une arête seulement si elle relie deux composantes différentes, sinon elle crée un cycle. Union-Find vérifie et fusionne les composantes. Arrêter après |V|−1 acceptations.
| Étape | Sommet / arête | File / ensemble définitif / coût | Kruskal |
|---|---|---|---|
| 0 | — | 0 | — |
| 1 | BC (1) | 1 | Choisie |
| 2 | AC (2) | 3 | Choisie |
| 3 | DE (2) | 5 | Choisie |
| 4 | EF (3) | 8 | Choisie |
| 5 | AB (4) | 8 | Rejetée : cycle |
| 6 | BD (5) | 13 | Choisie |
Ordre : BC(1), AC(2), DE(2), EF(3), AB(4), BD(5). AB est rejetée : A et B sont déjà reliés via C, donc elle fermerait A–C–B–A. BD relie {A,B,C} à {D,E,F}. Coût : 1+2+2+3+5=13. DF(6), CD(8), CE(10) ne sont plus nécessaires.
Pourquoi cela fonctionne : échange
- Invariant : un arbre couvrant minimal T contient les arêtes F déjà choisies. C’est vrai pour F vide. Soit e la prochaine arête acceptée entre deux composantes de F.
- Si e appartient à T, rien à changer. Sinon son ajout crée un cycle unique. Ce cycle contient une arête f sortant de la composante d’une extrémité de e ; f n’appartient pas à F. De plus w(f)≥w(e), car une arête plus légère traversant cette composante aurait déjà été examinée et aurait fusionné les composantes.
- Remplacer f par e conserve un arbre sans augmenter le coût. Comme T était minimal, le nouvel arbre est minimal et contient F ainsi que e. L’invariant est préservé. Après |V|−1 choix, notre arbre est un MST.
Tri : O(|E| log |E|). Union-Find avec compression des chemins et union par rang : O(|E| α(|V|)) au total, presque linéaire. Mémoire O(|V|+|E|), arêtes triées comprises. Les poids négatifs sont permis. Un graphe non connexe donne une forêt couvrante minimale.
Princeton · Algorithms, 4th Edition — Kruskal
Ici Dijkstra et Kruskal donnent 13 et les mêmes arêtes par coïncidence. Dans le triangle AB=2, AC=2, BC=1, l’arbre des plus courts chemins depuis A utilise AB et AC, coût total 4. Un MST utilise BC et une arête de poids 2, total 3 ; un trajet depuis A coûte alors 3 au lieu de 2. Les objectifs sont différents.