Skip to main content Link Search Menu Expand Document (external link)

Today we’re visualizing graph algorithms on Paris.
Then you’ll have to validate at least one problem.

Paris graph Jupyter notebook

Question 0
A drunkard is making a random walk in Paris. What does it look like?

You can visualize using matplotlib plt.scatter with a different color c='r' or Folium.

Question 1
Compare a shortest path between two points by walk and by car. Plot both paths.

When we are walking, we can take both sides of the street; and the cost is the length. When we are traveling by car, we have to respect the sides given in the dataset, and the cost is the duration.

Question 2
RATP is asking you to build metro lines that connect any two points of Paris. Cost of digging a line is proportional to its length. What should you do?
Question 3
We want to visit every station of Paris exactly once while walking as few as possible. Write an algorithm for this.
stations = [
    "Gare d'Austerlitz",
    "Gare de Bercy",
    "Gare de l'Est",
    "Gare de Lyon",
    "Gare Montparnasse",
    "Gare du Nord",
    "Gare Saint-Lazare"