Séance 7 — Implémentation de l'algorithme de Dijkstra¶
VERSION corrigée
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]:
Copied!
# 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 [ ]:
Copied!
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"
Réponse Taf6-1 : il suffit de recopier la lsite de liste de la 1ère partie de l'évaluation
In [8]:
Copied!
# la structure de données pour le Graphe est la liste de liste de la 1ère partie:
Graphe = [[0, 4, 2, 0, 0, 0, 0, 0 ],
[4, 0, 6, 0, 5, 0, 0, 0 ],
[2, 6, 0, 3, 0, 0, 0, 5 ],
[0, 0, 3, 0, 0, 3, 4, 1 ],
[0, 5, 0, 0, 0, 2, 0, 0 ],
[0, 0, 0, 3, 2, 0, 7, 0 ],
[0, 0, 0, 4, 0, 7, 0, 10],
[0, 0, 5, 1, 0, 0, 10, 0]]
# la structure de données pour le Graphe est la liste de liste de la 1ère partie:
Graphe = [[0, 4, 2, 0, 0, 0, 0, 0 ],
[4, 0, 6, 0, 5, 0, 0, 0 ],
[2, 6, 0, 3, 0, 0, 0, 5 ],
[0, 0, 3, 0, 0, 3, 4, 1 ],
[0, 5, 0, 0, 0, 2, 0, 0 ],
[0, 0, 0, 3, 2, 0, 7, 0 ],
[0, 0, 0, 4, 0, 7, 0, 10],
[0, 0, 5, 1, 0, 0, 10, 0]]
Réponse Taf6-2 : Les trois premieres vérifications mettent en évidence le retour de chacune des trois assertions ( 'Graphe' n'est pas de type 'list'; 's_debut' n'est pas de type 'int'; 's_debut' n'est pas un entier entre 0 et 7, puisque 'Graphe' est une liste de 8 éléments). La quatrième vérification ne crée pas d'AssertionError.
In [3]:
Copied!
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'obtention des plus courts chemins,
'poids', liste des poids de chaque sommet rangés dans l'ordre d'obtention des plus courts chemins,
'predecesseurs', liste des sommets "prédécesseur de chaque sommet" rangés dans l'ordre d'obtention des plus courts chemins,
"""
assert type(Graphe) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra("A",0)
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'obtention des plus courts chemins,
'poids', liste des poids de chaque sommet rangés dans l'ordre d'obtention des plus courts chemins,
'predecesseurs', liste des sommets "prédécesseur de chaque sommet" rangés dans l'ordre d'obtention des plus courts chemins,
"""
assert type(Graphe) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra("A",0)
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-3-d14470863b64> in <module> 13 assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe" 14 ---> 15 dijkstra("A",0) <ipython-input-3-d14470863b64> in dijkstra(Graphe, s_debut) 9 'predecesseurs', liste des sommets prédécesseur de chaque sommet rangés dans l'ordre d'exploration, 10 """ ---> 11 assert type(Graphe) == list, "Graphe doit être de type liste" 12 assert type(s_debut) == int, " s_debut doit être un entier " 13 assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe" AssertionError: Graphe doit être de type liste
In [4]:
Copied!
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra(Graphe,"A")
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra(Graphe,"A")
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-4-4268aa1c9000> in <module> 13 assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe" 14 ---> 15 dijkstra(Graphe,"A") <ipython-input-4-4268aa1c9000> in dijkstra(Graphe, s_debut) 10 """ 11 assert type(Graphe) == list, "Graphe doit être de type liste" ---> 12 assert type(s_debut) == int, " s_debut doit être un entier " 13 assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe" 14 AssertionError: s_debut doit être un entier
In [6]:
Copied!
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra(Graphe,8)
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra(Graphe,8)
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-6-c0b62074927f> in <module> 13 assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe" 14 ---> 15 dijkstra(Graphe,8) <ipython-input-6-c0b62074927f> in dijkstra(Graphe, s_debut) 11 assert type(Graphe) == list, "Graphe doit être de type liste" 12 assert type(s_debut) == int, " s_debut doit être un entier " ---> 13 assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe" 14 15 dijkstra(Graphe,8) AssertionError: s_debut doit être dans la plage d'indice de Graphe
In [7]:
Copied!
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra(Graphe,0)
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
dijkstra(Graphe,0)
Réponse Taf6-3 : La quatrième vérification n'ayant pas créé d'AssertionError, elle valide à priori l'appel de la fonction 'dijkstra' avec les bons paramètres. La valeur '0' correspond au premier sommet du graphe dans la structure de liste de liste qui est la liste [0, 4, 2, 0, 0, 0, 0, 0 ] indiquant bien que le sommet A a un arc de distance 4 avec B et un arc avec C de distance 2.
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 [ ]:
Copied!
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
Réponse Taf7 : Les deux lignes manquantes sont de la même forme que les deux précédentes en remplaçant la variable 'predecesseurs' par la variable 'poids' de type liste, et la valeur '-1' par 'infini' .
In [ ]:
Copied!
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
poids = [infini for sommet in range(len(Graphe))] # initialisation des poids à l'infini
poids[s_debut] = 0 # 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
poids = [infini for sommet in range(len(Graphe))] # initialisation des poids à l'infini
poids[s_debut] = 0 # 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 [ ]:
Copied!
# 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 [ ]:
Copied!
# 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 [ ]:
Copied!
# 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 [ ]:
Copied!
# 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 [ ]:
Copied!
#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
Réponse Taf8 : La bonne réponse au QCM4 est la 3. D'ou le script complété ci-dessous.
In [ ]:
Copied!
#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été ci-dessous à partir de la réponse 3 du QCM4"""
#Algo: mise à jour poids et prédécesseur du plus proche voisin
if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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été ci-dessous à partir de la réponse 3 du QCM4"""
#Algo: mise à jour poids et prédécesseur du plus proche voisin
if poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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 [ ]:
Copied!
#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
Réponse Taf9 : Les commentaires doivent mettre en évidence le rôle et l'initialisation des variables locales à cette partie du script, les conditions de la boucle fort et du test conditionnel .
In [ ]:
Copied!
#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 # initialisation du poids en cours de calcul à une valeur infinie
s_mini = -1 # initialisation du sommet de poids minimal à 'non défini'
for s in E_sommets: # Pour chaque sommet non définitivement calculés:
if poids[s] < poids_local: # Si le poids du sommet actuel est inférieur au poids local:
poids_local = poids[s] # le poids local est remplacé par la valeur (inférieure) du sommet actuel
s_mini = s # le sommet de poids minimal est le sommet actuel
#----------> 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 poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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 # initialisation du poids en cours de calcul à une valeur infinie
s_mini = -1 # initialisation du sommet de poids minimal à 'non défini'
for s in E_sommets: # Pour chaque sommet non définitivement calculés:
if poids[s] < poids_local: # Si le poids du sommet actuel est inférieur au poids local:
poids_local = poids[s] # le poids local est remplacé par la valeur (inférieure) du sommet actuel
s_mini = s # le sommet de poids minimal est le sommet actuel
#----------> 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 poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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 [ ]:
Copied!
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])
Réponse Taf10 : La présence de la documentation de la fonction et des assertions est un plus dans la reconstitution de la fonction. L'accompagnement au bon fonctionnement du programme final se fera au prix de malus suivant le niveau d'aide apportée et le type d'erreur corrigé.
In [12]:
Copied!
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
#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
poids = [infini for sommet in range(len(Graphe))] # initialisation des poids à l'infini
poids[s_debut] = 0 # 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
#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 # initialisation du poids en cours de calcul à une valeur infinie
s_mini = -1 # initialisation du sommet de poids minimal à 'non défini'
for s in E_sommets: # Pour chaque sommet non définitivement calculés:
if poids[s] < poids_local: # Si le poids du sommet actuel est inférieur au poids local:
poids_local = poids[s] # le poids local est remplacé par la valeur (inférieure) du sommet actuel
s_mini = s # le sommet de poids minimal est le sommet actuel
#----------> 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 poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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
return E_calcules, poids, predecesseurs
# 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):
""" 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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
#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
poids = [infini for sommet in range(len(Graphe))] # initialisation des poids à l'infini
poids[s_debut] = 0 # 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
#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 # initialisation du poids en cours de calcul à une valeur infinie
s_mini = -1 # initialisation du sommet de poids minimal à 'non défini'
for s in E_sommets: # Pour chaque sommet non définitivement calculés:
if poids[s] < poids_local: # Si le poids du sommet actuel est inférieur au poids local:
poids_local = poids[s] # le poids local est remplacé par la valeur (inférieure) du sommet actuel
s_mini = s # le sommet de poids minimal est le sommet actuel
#----------> 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 poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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
return E_calcules, poids, predecesseurs
# 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])
Out[12]:
True
Optionnel, Travail à faire 11: Complexité expérimentale¶
En utilisant le script complet de la fonction 'dijkstra', effectuer la mesure de temps d'éxécution dans plusieurs situations pour évaluer expérimentalement le coût de cet algorithme.
In [ ]:
Copied!
from random import randint
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
#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
poids = [infini for sommet in range(len(Graphe))] # initialisation des poids à l'infini
poids[s_debut] = 0 # 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
#---------->fin d'initialisation
#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 # initialisation du poids en cours de calcul à une valeur infinie
s_mini = -1 # initialisation du sommet de poids minimal à 'non défini'
for s in E_sommets: # Pour chaque sommet non définitivement calculés:
if poids[s] < poids_local: # Si le poids du sommet actuel est inférieur au poids local:
poids_local = poids[s] # le poids local est remplacé par la valeur (inférieure) du sommet actuel
s_mini = s # le sommet de poids minimal est le sommet actuel
#----------> 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 poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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
return E_calcules, poids, predecesseurs
def matrice(i,j): # fonction qui génère une liste de 'i' liste de 'j' éléments
# avec des valeurs entières aléatoires entre 0 et 20
return [[randint(0,20) for q in range(0,j)] for p in range(0,i)]
for n_elt in range(6,20,1): # test de durée d'éxécution de la fonction 'dijkstra' pour des graphes de 6 à 20 sommets
M = matrice(n_elt, n_elt)
%timeit dijkstra(M,0)
from random import randint
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) == list, "Graphe doit être de type liste"
assert type(s_debut) == int, " s_debut doit être un entier "
assert s_debut in [i for i in range(len(Graphe))], "s_debut doit être dans la plage d'indice de Graphe"
#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
poids = [infini for sommet in range(len(Graphe))] # initialisation des poids à l'infini
poids[s_debut] = 0 # 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
#---------->fin d'initialisation
#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 # initialisation du poids en cours de calcul à une valeur infinie
s_mini = -1 # initialisation du sommet de poids minimal à 'non défini'
for s in E_sommets: # Pour chaque sommet non définitivement calculés:
if poids[s] < poids_local: # Si le poids du sommet actuel est inférieur au poids local:
poids_local = poids[s] # le poids local est remplacé par la valeur (inférieure) du sommet actuel
s_mini = s # le sommet de poids minimal est le sommet actuel
#----------> 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 poids[s_voisin] > poids[s_mini] + Graphe[s_mini][s_voisin] and Graphe[s_mini][s_voisin] !=0: # si le chemin est plus court et il y a existance d'un arc:
poids[s_voisin] = poids[s_mini] + Graphe[s_mini][s_voisin] # mise à jour du poids du plus proche voisin
predecesseurs[s_voisin] = s_mini # 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
return E_calcules, poids, predecesseurs
def matrice(i,j): # fonction qui génère une liste de 'i' liste de 'j' éléments
# avec des valeurs entières aléatoires entre 0 et 20
return [[randint(0,20) for q in range(0,j)] for p in range(0,i)]
for n_elt in range(6,20,1): # test de durée d'éxécution de la fonction 'dijkstra' pour des graphes de 6 à 20 sommets
M = matrice(n_elt, n_elt)
%timeit dijkstra(M,0)
Constatation et interrogation:
En doublant le nombre $n$ de sommets du graphe, on constate approximativement un doublement du temps d'éxécution $T$ de cette implémentation de l'algorithme de Dijkstra. Pour les étudiantes ayant fait l'annexe optionnelle sur la complexité théorique : ceci n'est pas en accord avec le calcul théorique qui y est fait. Cherchez l'erreur (?)
In [20]:
Copied!
def matrice(i,j):
return [[randint(0,20) for q in range(0,j)] for p in range(0,i)]
#import timeit
import time
for n_elt in range(6,20,1):
t1 = time.process_time()
for i in range(100):
M = matrice(n_elt, n_elt)
dijkstra(M, 0)
t2 = time.process_time()
print(" 100 graphes de ", n_elt," sommets pour une durée de ", t2-t1, " secondes.")
def matrice(i,j):
return [[randint(0,20) for q in range(0,j)] for p in range(0,i)]
#import timeit
import time
for n_elt in range(6,20,1):
t1 = time.process_time()
for i in range(100):
M = matrice(n_elt, n_elt)
dijkstra(M, 0)
t2 = time.process_time()
print(" 100 graphes de ", n_elt," sommets pour une durée de ", t2-t1, " secondes.")
100 graphes de 6 sommets pour une durée de 0.015600100000000339 secondes. 100 graphes de 7 sommets pour une durée de 0.015600100000000339 secondes. 100 graphes de 8 sommets pour une durée de 0.031200200000000677 secondes. 100 graphes de 9 sommets pour une durée de 0.046800300000001016 secondes. 100 graphes de 10 sommets pour une durée de 0.031200200000000677 secondes. 100 graphes de 11 sommets pour une durée de 0.031200200000000677 secondes. 100 graphes de 12 sommets pour une durée de 0.046800300000001016 secondes. 100 graphes de 13 sommets pour une durée de 0.062400400000001355 secondes. 100 graphes de 14 sommets pour une durée de 0.046800300000001016 secondes. 100 graphes de 15 sommets pour une durée de 0.062400400000001355 secondes. 100 graphes de 16 sommets pour une durée de 0.0780005000000017 secondes. 100 graphes de 17 sommets pour une durée de 0.09360060000000203 secondes. 100 graphes de 18 sommets pour une durée de 0.09360060000000203 secondes. 100 graphes de 19 sommets pour une durée de 0.10920070000000237 secondes.
In [ ]:
Copied!