Séance 7 — Implémentation de l'algorithme de Dijkstra¶

VERSION ELEVE

On reprend ici l'intuition et le pseudo-code vus en Séance 6 pour les traduire en Python, sur le même graphe (circuits courts en Bretagne).

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

Travail à faire 6: Les données à traiter¶

Le graphe sera sous forme d'une liste de liste, comme dans la 1ère partie "méthode par force brute". 1- Reprenez cette liste et insérez la ci-dessous. 2- La fonction 'Dijkstra' est documentée (en rouge), complétez les trois assertions permettant de s'assurer de l'intégrité des données à traiter. Puis tester ces insertions avec 'dijkstra("A",0)', puis 'dijkstra(Graphe,"A")', puis 'dijkstra(Graphe,8)' et enfin 'dijkstra(Graphe,0) qui est la bonne écriture d'appel pour cette fonction. 3- Expliquer pourquoi '0' est saisi pour le paramètre 's-debut'?

In [2]:

# la structure de données pour le Graphe est la liste de liste de la 1ère partie: 
Graphe = 

# la structure de données pour le Graphe est la liste de liste de la 1ère partie: Graphe =

In [ ]:

def dijkstra(Graphe, s_debut):
    """  fonction: calculer les plus courts chemins à partir d'un sommet de départ vers chacun des autres sommets
    paramètres :
        'Graphe', un graphe sous forme d'une liste de liste,
        's_debut' un sommet de départ.
    renvoie:
        'E_calcules', liste des sommets rangés dans l'ordre d'exploration,
         'poids', liste des poids de chaque sommet rangés dans l'ordre d'exploration,
         'predecesseurs', liste des sommets prédécesseur de chaque sommet rangés dans l'ordre d'exploration,
    """
    assert type(Graphe)  ...            , "Graphe doit être de type liste"
    assert type(s_debut)  ...            , " s_debut doit être un entier "
    assert s_debut in [   ...        ], "s_debut doit être dans la plage d'indice de Graphe"

def dijkstra(Graphe, s_debut): """ fonction: calculer les plus courts chemins à partir d'un sommet de départ vers chacun des autres sommets paramètres : 'Graphe', un graphe sous forme d'une liste de liste, 's_debut' un sommet de départ. renvoie: 'E_calcules', liste des sommets rangés dans l'ordre d'exploration, 'poids', liste des poids de chaque sommet rangés dans l'ordre d'exploration, 'predecesseurs', liste des sommets prédécesseur de chaque sommet rangés dans l'ordre d'exploration, """ assert type(Graphe) ... , "Graphe doit être de type liste" assert type(s_debut) ... , " s_debut doit être un entier " assert s_debut in [ ... ], "s_debut doit être dans la plage d'indice de Graphe"

Travail à faire 7: Initialisation de l'algorithme¶

En reprenant les éléments de l'algorithme fournis au Taf2 et au Taf4, compléter les deux lignes manquantes de la partie "Algo: initialisation" du script, ci-dessous.

In [ ]:

def dijkstra(Graphe, s_debut):
    #Algo: Initialisation
    infini=float("inf")                                   # définition d'une valeur infinie
    predecesseurs = [-1 for sommet in range(len(Graphe))] # initialisation des prédecesseurs à non parcouru (-1)
    predecesseurs[s_debut] = 0                            # sauf le sommet de départ qui est le prédécesseur de lui-même
    ...                                                   # initialisation des poids à l'infini
    ...                                                   # sauf le sommet de départ de poids nul
    E_sommets = [i for i in range(len(Graphe))]           # initialisation de l'ensemble des sommets du graphe
    E_calcules = []                                       # création de la liste des calculés, vide au départ

def dijkstra(Graphe, s_debut): #Algo: Initialisation infini=float("inf") # définition d'une valeur infinie predecesseurs = [-1 for sommet in range(len(Graphe))] # initialisation des prédecesseurs à non parcouru (-1) predecesseurs[s_debut] = 0 # sauf le sommet de départ qui est le prédécesseur de lui-même ... # initialisation des poids à l'infini ... # sauf le sommet de départ de poids nul E_sommets = [i for i in range(len(Graphe))] # initialisation de l'ensemble des sommets du graphe E_calcules = [] # création de la liste des calculés, vide au départ

Travail à faire 8: Partie "Mise à jour, poids et prédécesseur du plus proche voisin" de l'algorithme¶

En reprenant les éléments de l'algorithme fournis au Taf2 et au Taf4, complétez l'implémentation de la structure conditionnelle de la partie "Algo: Mise à jour, poids et prédécesseur du plus proche voisin" du script de la boucle principale, ci-dessous. Pour cela, répondez au QCM4 ci-dessous, puis placez la structure de code choisie dans le script de la boucle principale situé plus bas.

$QCM4:$ Parmi les quatres extraits de script ci-dessous, un seul convient:

In [ ]:

# Réponse1
if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] = 0:
                    poids[s_voisin] = poids[s_mini] - Graphe[s_mini][s_voisin]                     
                    predecesseurs[s_voisin] = s_mini 

# Réponse1 if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] = 0: poids[s_voisin] = poids[s_mini] - Graphe[s_mini][s_voisin] predecesseurs[s_voisin] = s_mini

In [ ]:

# Réponse2
if poids[s_voisin] < poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] != 0:
                    poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin]                     
                    predecesseurs[s_mini] = s_voisin 

# Réponse2 if poids[s_voisin] < poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] != 0: poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] predecesseurs[s_mini] = s_voisin

In [ ]:

# Réponse3
if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] != 0:
                    poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin]                     
                    predecesseurs[s_voisin] = s_mini 

# Réponse3 if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] != 0: poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] predecesseurs[s_voisin] = s_mini

In [ ]:

# Réponse4
if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] or Graphe[s_mini][s_voisin] != 0:
                    poids[s_mini] = poids[s_voisin] + Graphe[s_mini][s_voisin]                     
                    predecesseurs[s_voisin] = s_mini 

# Réponse4 if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] or Graphe[s_mini][s_voisin] != 0: poids[s_mini] = poids[s_voisin] + Graphe[s_mini][s_voisin] predecesseurs[s_voisin] = s_mini

In [ ]:

#Algo: boucle principale
    while E_sommets:                # Tant que tous les sommets ne sont pas définitivement calculés:

        # Algo: recherche d'un sommet de distance minimale
        poids_local = infini            #
        s_mini = -1                     # 
        for s in E_sommets:             # 
            if poids[s] < poids_local:      # 
                poids_local = poids[s]          # 
                s_mini = s                      # 
        #----------> Algo: fin de recherche d'un sommet de distance minimale

        E_sommets.remove(s_mini)     # retrait du dernier sommet calculé à l'ensemble des sommets non définitivement calculés
        E_calcules.append(s_mini)    # ajout du dernier sommet calculé à la liste des sommets définitivement calculés
        for s_voisin in E_sommets:   # Pour chaque sommet voisin du dernier sommet calculé :
""" Partie du script à compléter ci-dessous à partir du choix effectué au QCM4"""
            #Algo: mise à jour poids et prédécesseur du plus proche voisin
                    ...                                 # si le chemin st plus court et il y a existance d'un arc:
                    ...                                 # mise à jour du poids du plus proche voisin
                    ...                                 # mise à jour du prédécesseur du plus proche voisin
            #---------->  fin de mise à jour du poids et du prédécesseur du plus proche voisin
#---------->fin de boucle principale

#Algo: boucle principale while E_sommets: # Tant que tous les sommets ne sont pas définitivement calculés: # Algo: recherche d'un sommet de distance minimale poids_local = infini # s_mini = -1 # for s in E_sommets: # if poids[s] < poids_local: # poids_local = poids[s] # s_mini = s # #----------> Algo: fin de recherche d'un sommet de distance minimale E_sommets.remove(s_mini) # retrait du dernier sommet calculé à l'ensemble des sommets non définitivement calculés E_calcules.append(s_mini) # ajout du dernier sommet calculé à la liste des sommets définitivement calculés for s_voisin in E_sommets: # Pour chaque sommet voisin du dernier sommet calculé : """ Partie du script à compléter ci-dessous à partir du choix effectué au QCM4""" #Algo: mise à jour poids et prédécesseur du plus proche voisin ... # si le chemin st plus court et il y a existance d'un arc: ... # mise à jour du poids du plus proche voisin ... # mise à jour du prédécesseur du plus proche voisin #----------> fin de mise à jour du poids et du prédécesseur du plus proche voisin #---------->fin de boucle principale

Travail à faire 9: Partie "Recherche d’un sommet de distance minimale " de l'algorithme¶

En reprenant les éléments de l'algorithme fournis au Taf2 et au Taf4, commenter chaque ligne du script proposé pour la partie "Algo: Recherche d’un sommet de distance minimale" de façon à bien expliquer la solution implémentée pour obtenir le sommet "actuel" de poids minimal .

In [ ]:

#Algo: boucle principale
    while E_sommets:                # Tant que tous les sommets ne sont pas définitivement calculés:

        # Algo: recherche d'un sommet de distance minimale
        poids_local = infini            #
        s_mini = -1                     # 
        for s in E_sommets:             # 
            if poids[s] < poids_local:      # 
                poids_local = poids[s]          # 
                s_mini = s                      # 
        #----------> Algo: fin de recherche d'un sommet de distance minimale

        E_sommets.remove(s_mini)     # retrait du dernier sommet calculé à l'ensemble des sommets non définitivement calculés
        E_calcules.append(s_mini)    # ajout du dernier sommet calculé à la liste des sommets définitivement calculés
        for s_voisin in E_sommets:   # Pour chaque sommet voisin du dernier sommet calculé :

            #Algo: mise à jour poids et prédécesseur du plus proche voisin
            if ... and Graphe[s_mini][s_voisin] !=0: # si le chemin st plus court et il y a existance d'un arc:
                    ...                                           # mise à jour du poids du plus proche voisin
                    ...                                           # mise à jour du prédécesseur du plus proche voisin
            #---------->  fin de mise à jour du poids et du prédécesseur du plus proche voisin
#---------->fin de boucle principale

#Algo: boucle principale while E_sommets: # Tant que tous les sommets ne sont pas définitivement calculés: # Algo: recherche d'un sommet de distance minimale poids_local = infini # s_mini = -1 # for s in E_sommets: # if poids[s] < poids_local: # poids_local = poids[s] # s_mini = s # #----------> Algo: fin de recherche d'un sommet de distance minimale E_sommets.remove(s_mini) # retrait du dernier sommet calculé à l'ensemble des sommets non définitivement calculés E_calcules.append(s_mini) # ajout du dernier sommet calculé à la liste des sommets définitivement calculés for s_voisin in E_sommets: # Pour chaque sommet voisin du dernier sommet calculé : #Algo: mise à jour poids et prédécesseur du plus proche voisin if ... and Graphe[s_mini][s_voisin] !=0: # si le chemin st plus court et il y a existance d'un arc: ... # mise à jour du poids du plus proche voisin ... # mise à jour du prédécesseur du plus proche voisin #----------> fin de mise à jour du poids et du prédécesseur du plus proche voisin #---------->fin de boucle principale

Travail à faire 10: la fonction Dijkstra complète¶

Reconstituer ci dessous le script complet de la fonction 'dijkstra' et en effectuer le test. Si le test n'est pas probant, recherchez d'éventuelles erreurs flagrantes, et, si nécessaire appelez l'enseignant pour débloquer la situation.

In [ ]:

def dijkstra(Graphe, s_debut):
    

# le sommet s_debut choisi ici est "A", d'indice 0 dans E_sommets
dijkstra(Graphe,0)== ([0, 2, 1, 3, 7, 5, 4, 6], [0, 4, 2, 5, 9, 8, 9, 6], [0, 0, 0, 2, 1, 3, 3, 3])

def dijkstra(Graphe, s_debut): # le sommet s_debut choisi ici est "A", d'indice 0 dans E_sommets dijkstra(Graphe,0)== ([0, 2, 1, 3, 7, 5, 4, 6], [0, 4, 2, 5, 9, 8, 9, 6], [0, 0, 0, 2, 1, 3, 3, 3])