Graphes (UGA)

Plus courts chemins

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é

  2. Algorithmes et preuves
  

  • 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

  3. DAG et algorithme de Bellman
  

  • 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

  4. Poids positifs, algorithme de Dijkstra et tas binaire
  

  • 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)$  

• ---

• Transparents plus courts chemins File
• Feuille d'exercices plus courts chemins File
• One idea, one story: the physics of shortest paths to detect useless streets ! Page
• ---

• Test plus court chemin Quiz
• Trouver un plus court chemin lorsque les poids sont positifs Quiz
• Trouver un plus court chemin dans un DAG Quiz
• Vidéo (6min): Ordre topologique Page
• Exécuter l'algorithme de Bellman Ford Quiz
• "L'humour est le plus court chemin d'un homme à un autre."
  Georges Wolinski
  

• Implémentation de la structure de tas binaire et de l'algorithme de Dijkstra - Java Virtual programming lab
• Javadoc de Element.java File
• Javadoc de Arc.java File
• Javadoc de GrapheOriente.java File
• Javadoc de TasBinaire.java File