Résumé de section

    1. Graphes orientés
    2. Plus courts chemins
    3. DAG : l'algorithme de Bellman
    4. Poids positifs : l'algorithme de Dijkstra


    		Spyked math cheminement

    • 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 Fichier
      Les étudiants doivent
      Consulter
    • Feuille d'exercices plus courts chemins Fichier
      Les étudiants doivent
      Marquer comme terminé
    • One idea, one story: the physics of shortest paths to detect useless streets ! Page
      Les étudiants doivent
      Consulter
    • Test plus court chemin
      Les étudiants doivent
      Consulter
      Recevoir une note
      Obtenir une note minimale de réussite
    • Trouver un plus court chemin lorsque les poids sont positifs Test
      Les étudiants doivent
      Recevoir une note
      Obtenir une note minimale de réussite
    • Trouver un plus court chemin dans un DAG Test
      Les étudiants doivent
      Consulter
      Recevoir une note
      Obtenir une note minimale de réussite
    • Vidéo (6min): Ordre topologique Page
    • Exécuter l'algorithme de Bellman Ford Test
      Les étudiants doivent
      Marquer comme terminé
    • Les étudiants doivent
      Marquer comme terminé

      "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
      Les étudiants doivent
      Recevoir une note
    • Javadoc de Element.java Fichier
      Les étudiants doivent
      Consulter
    • Javadoc de Arc.java Fichier
      Les étudiants doivent
      Consulter
    • Javadoc de GrapheOriente.java Fichier
      Les étudiants doivent
      Consulter
    • Javadoc de TasBinaire.java Fichier
      Les étudiants doivent
      Consulter