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.
- Les trois parcours d'un même graphe
- Marquer au retrait : chiffrer ce que cela coûte
- Le parcours en profondeur itératif n'est pas le récursif
- Tri topologique : combien y en a-t-il, et que se passe-t-il s'il y a un cycle ?
- Bicolorabilité par un parcours en largeur
- Dijkstra, déroulé
- Combien d'insertions dans la file de priorité ?
- Floyd-Warshall, matrice après matrice
- L'ordre des boucles de Floyd-Warshall : le contre-exemple minimal
- Poids négatifs : ajouter une constante ne sauve rien
- Probleme – Rendre le chemin, pas seulement sa longueur
- Probleme – Bellman-Ford : ce que Dijkstra ne sait pas faire
- Probleme – Poids ou : une file à deux bouts au lieu d'un tas
- Probleme – Floyd-Warshall au-delà des distances
- Probleme – Un graphe sans circuit : les plus courts et les plus longs chemins