Plus courts chemins, avec poids: l’algorithme de Dijkstra

On considère le graphe suivant qui modélise un réseau routier:

from graph_networkx import examples
G = examples.dijkstra()
G.show()
../../_images/04-Dijkstra_2_0.png
from graph import examples
G = examples.dijkstra()
G.show()
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-1-0dc4531c70b2> in <module>
----> 1 from graph import examples
      2 G = examples.dijkstra()
      3 G.show()

~/work/Enseignement/AlgoAvancee/ComputerLab/2-ParcoursDeGraphes/graph.py in <module>
     36 
     37 
---> 38 class Graph:
     39 
     40     # Déclaration des attributs

~/work/Enseignement/AlgoAvancee/ComputerLab/2-ParcoursDeGraphes/graph.py in Graph()
     46     # À vous de choisir la structure de donnée pour les arêtes (edges)
     47     # Remplacer la ligne suivante par le code adéquat
---> 48     raise NotImplementedError("code non implanté ligne 49");
     49 
     50     def __init__(

NotImplementedError: code non implanté ligne 49

On souhaite calculer le plus court chemin entre deux sommets de ce graphe.

Exercice

  1. 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`
    """
    # YOUR CODE HERE
    raise NotImplementedError()
  1. Appliquez cette fonction au graphe G ci-dessus:

# YOUR CODE HERE
raise NotImplementedError()

En déduire la distance entre A et J, à mettre dans la variable distance_AJ:

# YOUR CODE HERE
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
  1. (Bonus) Adapter la fonction précédente pour qu’elle prenne deux sommets e et f et renvoie un plus court chemin entre e et f.

# YOUR CODE HERE
raise NotImplementedError()
  1. (Bonus) Instrumentez votre fonction pour en visualiser l’exécution.

# YOUR CODE HERE
raise NotImplementedError()

Problème 1: Le chemin le plus rapide en métro de Montgallet à Billancourt ?

../../_images/metro-paris.gif
  1. 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.

  2. Écrire une fonction qui lit le fichier et renvoie le graphe qu’il contient sous la forme d’un objet de type Graph.

  3. Utilisez la fonction dijkstra pour calculer un plus court chemin de Montgallet à Billancourt!

# YOUR CODE HERE
raise NotImplementedError()