Reconnaître un algorithme dans un cours est plus facile que choisir le bon devant une nouvelle situation. Un énoncé parle de routes, de câbles ou de livraisons ; il n'annonce pas toujours la quantité à optimiser. Ce dernier chapitre propose une méthode de décision. Nous partirons de la question, vérifierons les hypothèses, comparerons les ressources et construirons un petit certificat pour contrôler la réponse.
Pour une livraison, « trouver le meilleur trajet » reste trop vague. Cherche-t-on le moins de correspondances, la dépense minimale ou la visite de tous les clients ? Pour installer un réseau, veut-on minimiser les câbles, conserver des trajets rapides ou résister à une panne ? Chaque formulation demande un objet différent : un chemin, un ensemble d'arêtes, un ordre de tâches ou une répartition de quantités.
Une bonne phrase de départ précise l'entrée, la sortie et le critère de réussite. Par exemple : « Étant donnés des arcs de coûts non négatifs et une source, produire les coûts minimaux vers les sommets accessibles ». Cette phrase oriente vers Dijkstra et évite de lui demander implicitement une tournée complète.
BFS minimise un nombre de liaisons lorsque chaque liaison compte pareil. Dijkstra accepte des coûts positifs ou nuls. Bellman-Ford accepte les poids négatifs, mais doit signaler les sommets affectés par un circuit absorbant accessible. Floyd-Warshall produit toutes les paires et doit interpréter sa diagonale avant d'annoncer les distances.
Un ordre topologique exige un graphe orienté sans cycle. Un arbre couvrant minimal concerne un réseau non orienté ; si le réseau est déconnecté, on obtient une forêt. Un flot exige des capacités non négatives, une source et un puits distincts, ainsi que des contraintes de conservation. Ces conditions ne sont pas des détails que l'on ajoute après le calcul.
Vérifier toutes les données peut demander du travail, mais cette dépense est souvent linéaire dans leur taille. Elle évite une réponse plausible et fausse. Dans une application, le contrat d'entrée peut garantir certaines propriétés ; il faut alors savoir où elles sont contrôlées et ce qui se produit si elles deviennent invalides.
| Question | Méthode | Hypothèse |
|---|---|---|
| Nombre minimal de liaisons | BFS | Chaque liaison compte pareil |
| Explorer, détecter des cycles | DFS | Adapter le test à l’orientation |
| Ordre de dépendances | DFS, fins inversées | Graphe orienté sans cycle |
| Coûts depuis une source | Dijkstra | Poids non négatifs |
| Coûts avec poids négatifs | Bellman-Ford | Diagnostiquer les cycles accessibles |
| Toutes les paires | Floyd-Warshall | Interpréter la diagonale |
| Installation minimale | Kruskal ou Prim | Non orienté, forêt si déconnecté |
| Débit maximal | Edmonds-Karp | Capacités et conservation |
Le tableau est une aide, pas un détecteur automatique fondé sur quelques mots. Le mot « minimum » apparaît dans plusieurs problèmes. La question « relier tous les sites au moindre coût » peut désigner des câbles installés ou une tournée qui visite chaque site. Le premier cas correspond à un arbre couvrant minimal ; le second ne se résout généralement pas par Kruskal.
| Algorithme | Variante | Temps | Mémoire auxiliaire |
|---|---|---|---|
| BFS / DFS | Listes | O(n + m) | O(n) |
| Tri topologique DFS | Listes, DAG | O(n + m) | O(n) |
| Dijkstra | Tas à diminution de clé | O((n + m) log n) | O(n) |
| Dijkstra | Matrice, minimum linéaire | O(n²) | O(n) |
| Bellman-Ford | Passages sur les arcs | O(nm) + O(n) initialisation | O(n), sans historique |
| Floyd-Warshall | Matrice | O(n³) | O(n²) |
| Kruskal | Tri + union-find | O(m log m) + O(m α(n)) + O(n) | O(n), hors tri et arêtes |
| Prim | Tas à diminution de clé | O((n + m) log n) | O(n) |
| Prim | Matrice | O(n²) | O(n) |
| Edmonds-Karp | Listes résiduelles | O(nm²) | O(n + m) |
BFS et DFS exploitent des listes d'adjacence pour visiter le graphe en O(n + m). Une matrice peut faire passer ce travail à O(n²). Dijkstra et Prim profitent d'une file de priorité ; la version à sélection linéaire reste parfois simple et efficace sur un petit graphe dense. Kruskal paie principalement le tri de toutes les arêtes.
Bellman-Ford effectue plusieurs balayages des arcs. Floyd-Warshall paie un coût cubique même si beaucoup de liaisons sont absentes. Edmonds-Karp utilise BFS dans un réseau résiduel, mais ce BFS se répète après les augmentations : sa complexité globale n'est donc pas celle d'un seul parcours.
Pour un chemin annoncé, vérifiez que chaque liaison existe dans le bon sens et que la somme des poids correspond au coût publié. Pour BFS, les niveaux doivent respecter l'organisation par couches. Pour un ordre topologique, chaque arc doit pointer d'un sommet placé plus tôt vers un sommet placé plus tard.
Pour un arbre couvrant, contrôlez la présence de tous les sommets, l'absence de cycle, la connexité et le nombre d'arêtes. Kruskal et Prim doivent donner le même coût minimal, même si leurs choix diffèrent en cas d'égalité. Sur un tout petit graphe, on peut énumérer les candidats pour ajouter une vérification exhaustive.
Pour les distances positives, comparez Dijkstra à Bellman-Ford. Pour toutes les paires, comparez chaque ligne de Floyd-Warshall à un calcul depuis la source correspondante. Pour un flot, vérifiez les capacités et la conservation, puis exhibez une coupe de capacité égale à la valeur trouvée. Cette dernière égalité prouve directement l'optimalité.
Essayez un sommet isolé, un graphe déconnecté, des poids nuls, plusieurs solutions de même coût et des arcs à sens unique. Pour les poids négatifs, testez séparément un arc négatif sans cycle, un cycle accessible et un cycle situé hors de la zone accessible. Ces situations demandent des statuts différents.
Le contre-exemple S → A de poids 2, S → B de poids 5 et B → A de poids −4 vérifie réellement l'échec de Dijkstra classique : A est figé à 2 alors que le coût minimal vaut 1. Un exemple contenant simplement une valeur négative ne suffit pas à montrer un échec ; il faut exécuter la version précise de l'algorithme.
Décrire les sommets, les liaisons et les unités
Formuler la sortie et l'objectif
Vérifier les préconditions
Choisir représentation et algorithme
Exécuter en conservant une trace utile
Contrôler la réponse par un certificat
Annoncer temps, mémoire et situations impossiblesLa trace utile dépend de la question. Pour Dijkstra, montrez les finalisations et les améliorations. Pour Kruskal, montrez les arêtes acceptées ou refusées et les groupes. Pour un flot, montrez les chemins augmentants, leurs goulots et la coupe finale. Une liste de nombres sans convention ni état initial est difficile à vérifier, même si chaque nombre est exact.
On veut le moins de correspondances entre deux stations, chaque liaison comptant une étape. Quel outil convient ?
BFS convient : il minimise le nombre de liaisons. Il faut suivre le sens des arcs si certaines liaisons sont à sens unique. Les prix éventuels sont hors de l'objectif ; les minimiser demanderait un problème pondéré distinct.
Un petit réseau orienté doit répondre à des coûts entre tous les couples. Certains arcs sont négatifs. Quel calcul proposer ?
Floyd-Warshall est adapté à un résultat toutes paires de taille raisonnable. Il faut vérifier la diagonale et signaler les couples affectés par un cycle négatif. Une matrice finie ne doit pas masquer un coût non borné.
Deux programmes renvoient des arbres différents de même coût. Est-ce nécessairement une erreur ?
Non. Des égalités de poids peuvent produire plusieurs arbres minimaux. Vérifiez que chaque sortie couvre tous les sommets, est connexe et sans cycle, puis comparez les coûts à une borne ou à une méthode indépendante.
Un flot laisse de la place sur un arc arrivant au puits. Peut-on conclure que le flot n'est pas maximal ?
Non. Il faut un chemin augmentant complet depuis la source. Dans notre réseau, BT garde une unité libre, mais la coupe sortant de S est déjà saturée à 15. Cette coupe prouve qu'aucune augmentation globale n'est possible.
Questions / Réponses
Ajouter un commentaire