Centrale Lille - Algo II - TP2

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"