Skip to main content
grasp.study
About
Explore
Pricing
Log in
Try it for free
Back to course
👋
Welcome to a Grasp lesson
Create a free account
to keep studying and create your own study path.
Agrégation Informatique: Première Année Préparation
·
Module 8
Algorithmes de Graphes Avancés
1
Dijkstra avec File de Priorité
Implémenter l'algorithme de Dijkstra en utilisant une file de priorité pour les plus courts chemins à poids positifs.
2
Preuve de correction de Dijkstra par récurrence
Prouver la correction de l'algorithme de Dijkstra par récurrence sur l'ensemble des sommets finalisés.
Bellman-Ford: Poids Négatifs et Détection de Cycles
Implémenter l'algorithme de Bellman-Ford et expliquer sa capacité à gérer les poids négatifs et à détecter les cycles négatifs.
4
Dijkstra vs Bellman-Ford: Cas d'usage et Complexité
Comparer les cas d'usage et les complexités de Dijkstra et Bellman-Ford.
5
Implémentation de l'algorithme de Prim
Implémenter l'algorithme de Prim pour trouver un arbre couvrant de poids minimum.
6
Union-Find : Optimisations
Implémenter la structure Union-Find avec compression de chemins et union par rang.
7
Algorithme de Kruskal avec Union-Find
Implémenter l'algorithme de Kruskal en utilisant la structure Union-Find.
Previous module
Graphes : Parcours et Algorithmes Fondamentaux
Next module
Programmation Dynamique