Graphes (UGA L3 MI)

Compétences

• 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 : $d^-(u)$, $d^+(u)$, $d(u, v)$