TNSI : TD ALGORITHME DE DIJKSTRA ITÉRATIF, PLUS COURT CHEMIN⚓︎

Introduction⚓︎

Ce TD étudie l'Algorithme de Dijkstra qui généralise le Parcours en Largeur itératif, ou BFS - Breadth First Search itératif, dans le cas des graphes Pondérés avec des Poids Positifs \(\gt 0\) (Non Orientés ou Orientés). En particulier, l'Algorithme de Dijkstra permet de déterminer un plus court chemin entre deux sommets d'un graphe pondéré de poids positifs.

Dans une première partie du TD, Le graphe sera considéré Non Orienté Pondéré : Nous utiliserons dans ce cas notre classe Graphe Non Orienté Pondéré. On s'intéressera par exemple à la distance minimale entre deux villes A et B, mais sans tenir compte des sens interdits.

Dans une deuxième partie du TD, le graphe sera considéré Orienté Pondéré :
Nous utiliserons dans ce cas notre Graphe Orienté Pondéré. On s'intéressera par exemple à la distance minimale entre deux points A et B du réseau routier , mais en tenant compte cette fois-ci des sens interdits, par exemple, dans cette petite peuplade marseillaise:

Pseudo-Code de l'Algorithme de Dijkstra⚓︎

Introduction à l'Algorithme de Dijkstra (9min)

Pseudo-Code de Dijkstra, et
Structures de Données Utilisées (22min43)

Plus Court Chemin et Distance maximale d'un chemin dans un Graphe⚓︎

Expliquer pourquoi (par exemple grâce à un raisonnement par l'absurde) un plus court chemin entre deux sommets distincts d'un graphe ne peut pas contenir de cycle...
Quelle est la distance maximale, en tenant compte des poids du graphe, d'une chaîne/chemin orienté(e) sans cycles entre deux sommets distincts? et si les sommets ne sont pas distincts? Aide :
- la chaîne/chemin orienté de distance maximale passe (au plus) une fois, dans le pire des cas, par tous les sommets du graphe
- on pourra exprimer cette distance maximale en fonction du poids_max() d'une arête/arc du graphe, et du nombre n=self.ordre() de sommets.
En déduire une valeur possible pour une constante globale INF, qui modélisera une distance infinie, non atteignable, pour le plus court chemin (sans cycles..) entre deux sommets quelconques d'un graphe
Créer une méthode get_inf() qui renvoie la valeur distance infinie calculée à la question précédente.

Initialisation⚓︎

On reprend la phase d'initialisation du parcours en largeur, avec les différences/infos supplémentaires suivantes :

procédure initialise_parcours()
   # idem que parcours en largeur, plus :
   La constante globale INF prend la valeur get_int()
   Les sommets NonTraités sont tous les sommets du graphe
   La distance self.Dist[] de sdepart à tout sommet s vaut INF

Pseudo Code Algorithme de Dijkstra⚓︎

procédure dijkstra(Graphe, sdepart):
  Initialiser le parcours
  Tant que  l'ensemble des sommets NonTraites n'est pas vide:
      Déterminer le sommetMin parmi les NonTraites,
        qui soit à une distance minimale par rapport à sdepart
      Pour tout voisin v de sommetMin:
        mettre à jour les distances vers v, autrement dit :
         S'il existe un nouveau chemin plus court vers ce voisin v 
         (en passant par sommetMin), Alors:
            * On met à jour la nouvelle distance vers v
            * On fixe sommetMin comme Pere de v

Remarque L'implémentation de l'ensemble des Sommets NonTraites mériterait d'être détaillée : C'est en effet le point sensible car il influence grandement la complexité de cet algorithme. Pour bien faire, l'ensemble des sommets NonTraités devrait utiliser une structure de donnée qui soit :

une file de priorité, ou
un tas binaire, etc.... ou
(au minimum) de type ensemble set en Python : (faites-le si vous le souhaitez), car un type de données implémenté en Python par une table de Hachage (Test d'appartenance => Complexité en moyenne en \(O(1+k/n)\)). Par souci de simplicité pédagogique, nous nous contenterons d'utiliser une structure de donnée de type list Python.

Dijkstra dans un Graphe Non Orienté Pondéré⚓︎

Dans cette partie, on reprend la classe Graphe Non Orientée Pondérée : créez un premier fichier et nommez-le grapheNonOrientéPondéré.py

Écrire une méthode trouveMin() qui :
- fait la supposition que la variable self.NonTraites est déjà renseignée (ou initialisée)
- renvoie :
  - le sommet sommetMin, parmi les sommets NonTraités, qui se trouve à la plus courte distance de sdepart
  - ou bien l'entier -1, si tous les sommets NonTraités restants se trouvent à la distance INF de sdepart (pour signifier que tous les sommets NonTraités restants sont non atteignables par un parcours de dijkstra/en largeur depuis sdepart)

Écrire une méthode majDistances(sommetMin,v) qui met à jour (recalcule), conditionnellement (c'est-à-dire si besoin est), les Distances des chemins depuis sdepart, en passant par sommetMin, vers le voisin v (de sommetMin) Plus précisément :

procédure majDistances(sommetMin, v):
    S'il existe un chemin plus court vers `v` en passant par `sommetMin`
    Alors :
        * mettre à jour (recalculer) la distance minimale depuis `sdepart`, du voisin `v` de `sommetMin`
        * le `Pere` de `v` prend la valeur sommetMin

Écrire une méthode dijkstra(sdepart)->dict,dict qui implémente l'algorithme de Dijkstra, et qui renvoie deux dictionnaires:
- le dictionnaire d résumant toutes les distances minimales de sdepart à tout autre sommet du graphe
- le dictionnaire Pere résumant tous les sommets "Pères", pour tous les sommets du Graphe. Ainsi Pere[s] désigne le sommet juste avant le sommet s, par lequel le chemin minimal de sdebut à s doit obligatoirement passer pour arriver à s (il peut y avoir des chemins ex-aequo). Remarquer que cette fonction dijkstra détermine la valeur de la solution au problème initial posé: la distance minimale entre deux sommets. Mais elle NE fournit PAS en l'état la solution au problème posé: le chemin le plus court entre deux sommets.

Écrire une méthode plusCourtChemin(sdepart,sarrivee)->list qui donne le chemin le plus court: une liste contenant tous les sommets successifs du chemin minimal: de sdepart à sarrivee.

Principe de l'algorithme pour obtenir le plus court chemin entre sdepart et sarrivee:

fonction plusCourtChemin(sdepart, sarrivee):
    Exécuter la méthode dijkstra(sdepart)
    Initialisation: pcChemin est une liste vide
    s prend la valeur sarrivee
    Tant que le sommet s n'est pas le sommet de départ:
        ajouter s à pcChemin
        s prend la valeur Pere[s]   (lorsqu'il existe...)
    Ajouter sdepart à pcChemin
    Inverser la liste pcChemin     (car elle est parcourue à l'envers...)
    Renvoyer pcChemin

Créer une méthode toDotPlusCourtChemin(s:int, v:int, filename="testPlusCourtChemin.dot")->None, directement inspiré de la fonction toDot() que nous avons créée pour générer le fichier .dot pour un graphe, qui génère le fichier .dot (par défaut filename="testPlusCourtChemin.dot") tel que la couleur soit :
- ROUGE pour les sommets et les arêtes du Plus Court Chemin
- NOIR sinon : pour les sommets et les arêtes du graphe N'appartenant PAS au Plus Court Chemin
Créer la méthode showPlusCourtChemin(depart:int, arrivee:int, name="testPlusCourtchemin") qui affiche l'image d'un plus court chemin de depart à arrivee

Une vidéo avec des Tableaux⚓︎

Classiquement, et pour des non informaticiens, les vidéos présentant l'algorithme de Dijkstra, utilisent le tableau des Distances à sdepart pour une introduction pédagogique :

Une présentation manuelle classique avec le Tableau des Distances à sdepart

Cette manière de voir peut être intéressante, mais ne ressemble pas trop à notre implémentation Orientée Objet des Graphes. Nous ne l'utiliserons pas.

Dijkstra dans un Graphe Orienté Pondéré⚓︎

Dans cette partie, on reprend la classe Graphe Orientée Pondérée : créez un deuxième fichier et nommez-le grapheOrientéPondéré.py. Répondre exactement aux mêmes questions que pour les graphes Non Orientés, mais en adaptant tous les codes aux graphes Orientés :

Écrire une méthode trouveMin() qui :
- fait la supposition que la variable self.NonTraites est déjà renseignée (ou initialisée)
- renvoie :
  - le sommet sommetMin, parmi les sommets NonTraités, qui se trouve à la plus courte distance de sdepart
  - ou bien l'entier -1, si tous les sommets NonTraités restants se trouvent à la distance INF de sdepart (pour signifier que tous les sommets NonTraités restants sont non atteignables par un parcours de dijkstra/en largeur depuis sdepart)

procédure majDistances(sommetMin, v):
    S'il existe un chemin plus court vers `v` en passant par `sommetMin`
    Alors :
        * mettre à jour (recalculer) la distance minimale depuis `sdepart`, du voisin `v` de `sommetMin`
        * le `Pere` de `v` prend la valeur sommetMin

Écrire une méthode dijkstra(sdepart)->dict,dict qui implémente l'algorithme de Dijkstra, et qui renvoie deux dictionnaires:
- le dictionnaire d résumant toutes les distances minimales de sdepart à tout autre sommet du graphe
- le dictionnaire Pere résumant tous les sommets "Pères", pour tous les sommets du Graphe. Ainsi Pere[s] désigne le sommet juste avant le sommet s, par lequel le chemin minimal de sdebut à s doit obligatoirement passer pour arriver à s (il peut y avoir des chemins ex-aequo). Remarquer que cette fonction dijkstra détermine la valeur de la solution au problème initial posé: la distance minimale entre deux sommets. Mais elle NE fournit PAS en l'état la solution au problème posé: le chemin le plus court entre deux sommets.

Écrire une méthode plusCourtChemin(sdepart,sarrivee)->list qui donne le chemin le plus court: une liste contenant tous les sommets successifs du chemin minimal: de sdepart à sarrivee.

Principe de l'algorithme pour obtenir le plus court chemin entre sdepart et sarrivee:

fonction plusCourtChemin(sdepart, sarrivee):
    Exécuter la méthode dijkstra(sdepart)
    Initialisation: pcChemin est une liste vide
    s prend la valeur sarrivee
    Tant que le sommet s n'est pas le sommet de départ:
        ajouter s à pcChemin
        s prend la valeur Pere[s]   (lorsqu'il existe...)
    Ajouter sdepart à pcChemin
    Inverser la liste pcChemin     (car elle est parcourue à l'envers...)
    Renvoyer pcChemin

Créer une méthode toDotPlusCourtChemin(s:int, v:int, filename="testPlusCourtChemin.dot")->None, directement inspiré de la fonction toDot() que nous avons créée pour générer le fichier .dot pour un graphe, qui génère le fichier .dot (par défaut filename="testPlusCourtChemin.dot") tel que la couleur soit :
- ROUGE pour les sommets et les arcs du Plus Court Chemin
- NOIR sinon : pour les sommets et les arcs du graphe N'appartenant PAS au Plus Court Chemin
Créer la méthode showPlusCourtChemin(depart:int, arrivee:int, name="testPlusCourtchemin") qui affiche l'image d'un plus court chemin de depart à arrivee