Exercices corrigés — Parcours de graphes et plus courts chemins (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Marquer au retrait : chiffrer ce que cela coûte Exercice de TD
- Le parcours en profondeur itératif n'est pas le récursif Exercice de TD
- Bicolorabilité par un parcours en largeur Exercice de TD
- Combien d'insertions dans la file de priorité ? Exercice de TD
- Poids négatifs : ajouter une constante ne sauve rien Exercice de TD
- L'ordre des boucles de Floyd-Warshall : le contre-exemple minimal Exercice de TD
- Problème — Un graphe sans circuit : les plus courts et les plus longs chemins Exercice de TD
- Les trois parcours d'un même graphe Application directe du cours
- Tri topologique : combien y en a-t-il, et que se passe-t-il s'il y a un cycle ? Application directe du cours
- Dijkstra, déroulé Application directe du cours
- Floyd-Warshall, matrice après matrice Application directe du cours
- Problème — Rendre le chemin, pas seulement sa longueur Application directe du cours
- Problème — Bellman-Ford : ce que Dijkstra ne sait pas faire Application directe du cours
- Problème — Poids ou : une file à deux bouts au lieu d'un tas Application directe du cours
- Problème — Floyd-Warshall au-delà des distances Application directe du cours