Plus courts chemins
Résumé de section
-
- Graphes orientés
- Plus courts chemins
- DAG : l'algorithme de Bellman
- Poids positifs : l'algorithme de Dijkstra
-
Compétences
1. Problèmes- Décrire les trois problèmes de plus courts chemins
- Expliquer le principe de sous-optimalité
- Décrire les ingrédients d'un algorithme de plus court chemin
- Écrire l'algorithme BFS
- Pour les graphes non pondérés, décrire le certificat et la preuve que BFS renvoie bien les distances
- Démontrer qu'un DAG a toujours une source
- Décrire un algorithme pour trouver un ordre topologique
- Décrire l'algorithme de Bellman pour les plus courts chemins dans un DAG
- Appliquer l'algorithme de Bellman sur un exemple
- Décrire l'algorithme de Dijkstra pour les plus courts chemins lorsque les poids sont positifs
- Implémenter l'algorithme de Dijkstra
- Démontrer la validité de l'algorithme de Dijkstra
- Connaitre et Implémenter la structure de données tas binaire
- Calculer la complexité de l'algorithme de Dijkstra
Vocabulaire : Graphe orienté, arc, degré entrant, degré sortant, source, puits, chemin, longueur d'un chemin, circuit, graphe orienté pondéré, distance, DAG, ordre topologique, tas binaires
Notations :
, 
, 
-
-
-
Les étudiants doiventConsulter
-
Les étudiants doiventConsulterRecevoir une noteObtenir une note minimale de réussite
-
Les étudiants doiventRecevoir une noteObtenir une note minimale de réussite
-
Les étudiants doiventConsulterRecevoir une noteObtenir une note minimale de réussite
-
-
Les étudiants doiventMarquer comme terminé
"L'humour est le plus court chemin d'un homme à un autre."
Georges Wolinski -
Les étudiants doiventRecevoir une note
-
-
-
-
-
- Graphes orientés