Plus courts chemins, avec poids: l”algorithme de Dijkstra
Contenu
Plus courts chemins, avec poids: l”algorithme de Dijkstra¶
On considère le graphe suivant qui modélise un réseau routier:
from graph import examples
G = examples.dijkstra()
G.show()
On souhaite calculer le plus court chemin entre deux sommets de ce graphe.
Exercice
Implantez l’algorithme de Dijskstra
from graph import Graph, Node, Dict
infinity = float('inf')
def dijkstra(G: Graph, e: Node) -> Dict[Node, int]:
"""
Renvoie un dictionnaire associant à chaque sommet sa distance depuis `e`
"""
# VOTRE CODE ICI
raise NotImplementedError()
Appliquez cette fonction au graphe
G
ci-dessus:
# VOTRE CODE ICI
raise NotImplementedError()
En déduire la distance entre A
et J
, à mettre dans la variable distance_AJ
:
# VOTRE CODE ICI
raise NotImplementedError()
# Vérifie votre résultat sans dévoiler la solution, par la magie des fonctions de hachage :-)
import hashlib
h = hashlib.md5(bytes(distance_AJ)).hexdigest() == '2f6064003b888e403627e493532fc751'
distances = dijkstra(G, "A")
assert distances["A"] == 0
assert sum(distances.values()) == 2774
(Bonus) Adapter la fonction précédente pour qu’elle prenne deux sommets
e
etf
et renvoie un plus court chemin entree
etf
.
# VOTRE CODE ICI
raise NotImplementedError()
(Bonus) Instrumentez votre fonction pour en visualiser l’exécution.
# VOTRE CODE ICI
raise NotImplementedError()
Problème 1: Le chemin le plus rapide en métro de Montgallet à Billancourt ?¶

Le fichier metro_complet.txt contient la description d’un graphe modélisant le métro de Paris. Consultez son contenu pour en comprendre le format.
Écrire une fonction qui lit le fichier et renvoie le graphe qu’il contient sous la forme d’un objet de type
Graph
.Utilisez la fonction
dijkstra
pour calculer un plus court chemin de Montgallet à Billancourt!
# VOTRE CODE ICI
raise NotImplementedError()