Plus courts chemins
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
"L'humour est le plus court chemin d'un homme à un autre."
Georges Wolinski