Annexe optionnelle — Dijkstra avec une structure de données en dictionnaire¶

2ème mise en œuvre de l'algorithme de Dijkstra¶

VERSION ELEVE

Cette annexe est facultative, pour les étudiantes à l'aise en Python qui veulent aller plus loin après la Séance 7. Elle reprend le même algorithme que la Séance 7, mais avec une structure de données en dictionnaire plutôt qu'en liste — un bon exercice de transfert, mais pas un prérequis pour la suite du cours.

Conditions de réalisation :

• soit en complétant le notebook fourni soit sous la forme d'un fichier exécutable .py.

1- Présentation¶

Lors de l'activité précédente vous avez abouti à l'implémentation de l'algorithme de Dijkstra en vous appuyant sur une structure de données sous forme de liste. Pour rappel la structure du graphe utilisé: Cette fois ci je vous demande de construire une solution dans laquelle le graphe serait représenté sous la forme d'un dictionnaire dans lequel les clés serait les sommets.

2- Représentation du graphe par un dictionnaire¶

Travail 1 : définir la structure de donnée¶

Définir la structure de donnée pour représenter le graphe sous forme d’un dictionnaire. L'idée est de créer un dictionnaire dans lequel chaque sommet serait une clé. Et pour chaque clé on aurait à nouveau un dictionnaire contenant les sommets adjacents et la distance depuis le sommet précédent.

In [ ]:

#création du dictionnaire du graphe pondéré pour la recherche du plus court chemin
graph = {
'sommet': {'s_voisin1': distance, 's_voisin2': distance},
}

#création du dictionnaire du graphe pondéré pour la recherche du plus court chemin graph = { 'sommet': {'s_voisin1': distance, 's_voisin2': distance}, }

Vous avez la possibilité de revenir vers moi pour valider votre solution.

3- Implémentation de l'algorithme de Dijkstra¶

Travail 2 : implémenter votre solution¶

Votre solution sera documentée et s'appuiera sur le travail réalisé en classe.

In [ ]:

def initialisation(s_debut):
    """
    initialisation des variables permettant de parcourir le graphe
    Parameters
    ----------
    depart : string
        sommet de depart pour le parcours du graphe.
    Returns
    -------
    E_calcul : dict
        chemin en cours de calcul: poids et sommet précédent
        E_calcul = {s_debut:[poids,prédécesseur]}
        la distance au sommet de depart est nulle
    E_sommets : dict
        on met dans le dictionnaire provisoire les sommets adjacents 
        et leur poids par rapport au point de départ
        E_sommets = {s_voisin1: [poids,depart],...}
    """
    assert type(s_debut)  ...            , " s_debut doit être un caractère "

def initialisation(s_debut): """ initialisation des variables permettant de parcourir le graphe Parameters ---------- depart : string sommet de depart pour le parcours du graphe. Returns ------- E_calcul : dict chemin en cours de calcul: poids et sommet précédent E_calcul = {s_debut:[poids,prédécesseur]} la distance au sommet de depart est nulle E_sommets : dict on met dans le dictionnaire provisoire les sommets adjacents et leur poids par rapport au point de départ E_sommets = {s_voisin1: [poids,depart],...} """ assert type(s_debut) ... , " s_debut doit être un caractère "

In [ ]:

def Maj_poids(s_voisin,s_mini,poids, E_sommets):
    """
    Mise à jour du poids et du prédécesseur:
    si le sommet est nouveau : mettre à jour poids et prédecesseur
    si le sommet est déjà découvert: mettre à jour uniquement le poids
    
    Parameters
    ----------
    s_voisin : str
        sommet voisin
    s_mini : str
        sommet de poids mini
    poids : int
        poids du chemin le plus court 
    E_sommets : dict
        dictionnaire des chemins en cours d'exploration'

    Returns
    -------
    E_sommets : dict
        dictionnaire des chemins en cours d'exploration mise à jour
        avec le poids et le sommet de poids mini

    """

def Maj_poids(s_voisin,s_mini,poids, E_sommets): """ Mise à jour du poids et du prédécesseur: si le sommet est nouveau : mettre à jour poids et prédecesseur si le sommet est déjà découvert: mettre à jour uniquement le poids Parameters ---------- s_voisin : str sommet voisin s_mini : str sommet de poids mini poids : int poids du chemin le plus court E_sommets : dict dictionnaire des chemins en cours d'exploration' Returns ------- E_sommets : dict dictionnaire des chemins en cours d'exploration mise à jour avec le poids et le sommet de poids mini """

In [ ]:

def Dijkstra(graphe, s_debut):
    """
    Cette fonction implémente l'algorithme de dijkstra
    Parameters
    ----------
    graphe : dict
        DESCRIPTION. description du graphe
    s_debut : str
        DESCRIPTION. le sommet de départ

    Returns
    -------
    calcul: dict
        le résultat de l'algorithme de dijkstra

    """
    assert type(s_debut) == str, " s_debut doit être un caractère "
    assert type(graphe)   == dict, "graphe doit être un dictionnaire"
    
    
    #phase d'initialisation des données
    E_calcul,E_sommets=initialisation(s_debut)
    
    #tant que provisoire non vide
    while E_sommets!= {}:                                      
        #recherche de la distance la plus faible
        s_mini=min(E_sommets, key=E_sommets.get)
        #---------------------Partie à compléter
        
        
        
        #-------------------------------------        
    #fin while    
    return E_calcul    

def Dijkstra(graphe, s_debut): """ Cette fonction implémente l'algorithme de dijkstra Parameters ---------- graphe : dict DESCRIPTION. description du graphe s_debut : str DESCRIPTION. le sommet de départ Returns ------- calcul: dict le résultat de l'algorithme de dijkstra """ assert type(s_debut) == str, " s_debut doit être un caractère " assert type(graphe) == dict, "graphe doit être un dictionnaire" #phase d'initialisation des données E_calcul,E_sommets=initialisation(s_debut) #tant que provisoire non vide while E_sommets!= {}: #recherche de la distance la plus faible s_mini=min(E_sommets, key=E_sommets.get) #---------------------Partie à compléter #------------------------------------- #fin while return E_calcul

Travail 3: La vérification de votre implémentation¶

In [ ]:

def routage(calcul,depart,arrivee):   
    """
    Cette fonction donne le routage d'un sommet A au sommet B à partir
    du résultat obtenu par l'algorithme de dijkstra

    Parameters
    ----------
    calcul : dict
        résultat de l'algo de dijkstra
    depart : str
        sommet de départ
    arrivee : string
        sommet d'arrivée

    Returns
    -------
    routage : list
        le routage de A à B
    distance : int
        la distance

    """
    
    routage = [arrivee]
    distance=calcul[arrivee][0]
    #création de la liste de routage
    while routage[0]!= depart:                                     
        for key in calcul:
            if key==routage[0]:
                routage.insert(0,calcul[routage[0]][1])        
    return routage,distance

def routage(calcul,depart,arrivee): """ Cette fonction donne le routage d'un sommet A au sommet B à partir du résultat obtenu par l'algorithme de dijkstra Parameters ---------- calcul : dict résultat de l'algo de dijkstra depart : str sommet de départ arrivee : string sommet d'arrivée Returns ------- routage : list le routage de A à B distance : int la distance """ routage = [arrivee] distance=calcul[arrivee][0] #création de la liste de routage while routage[0]!= depart: for key in calcul: if key==routage[0]: routage.insert(0,calcul[routage[0]][1]) return routage,distance

In [ ]:

resultat = Dijkstra(graph,"A")
routage, distance= routage(resultat,"A","G")
print("le plus court chemin est: ", routage)
print("la distance parcourue : ", distance)

resultat = Dijkstra(graph,"A") routage, distance= routage(resultat,"A","G") print("le plus court chemin est: ", routage) print("la distance parcourue : ", distance)