TP n°16 (graphes) : Éléments de correction

$\require{color}$ $\require{xcolor}$ $\require{cancel}$ $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$ $\require{stmaryrd}$ $\newcommand{\ient}{[\![}$ $\newcommand{\rrbracket}{]\!]}$ $\newcommand{\llbracket}{[\![}$ $\newcommand{\fient}{]\!]}$ $\newcommand{\R}{\mathbb R}$ $\newcommand{\K}{\mathbb K}$ $\newcommand{\N}{\mathbb N}$ $\newcommand{\C}{\mathbb C}$ $\newcommand{\P}{\mathbb P}$ $\newcommand{\E}{\mathbb E}$ $\newcommand{\V}{\mathbb V}$ $\newcommand{\Z}{\mathbb Z}$ $\newcommand{\dt}{\mathrm d}$ $\newcommand{\sh}{\operatorname{sh}}$ $\newcommand{\ch}{\operatorname{ch}}$ $\newcommand{\id}{\operatorname{Id}}$ $\newcommand{\mat}{\operatorname{mat}}$ $\newcommand{\sp}{\operatorname{Sp}}$ $\newcommand{\In}{\operatorname{I}}$ $\newcommand{\vect}{\operatorname{Vect}\ }$ $\newcommand{\rg}{\operatorname{rg}}$ $\newcommand{\tr}{\operatorname{Tr}}$ $\newcommand{\dis}{\displaystyle}$ $\renewcommand{\Im}{\operatorname{Im}}$ $\newcommand{\im}{\operatorname{Im}}$ $\newcommand{\bordermatrix}[3]{ \begin{matrix} \begin{matrix}#1\end{matrix} & \\ #3 & \hspace{-1em} \begin{matrix}#2\end{matrix} \end{matrix}}$ $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$ $\newcommand{\fonctionsansnom}[4]{\left\{\begin{array}{ccl}#1 & \longrightarrow & #2\\#3 & \longmapsto & #4\end{array}\right.}$ $\newcommand{\revdots}{\mathinner{\mkern1mu\raise1pt{\kern7pt\hbox{.}}\mkern2mu\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}$ $\newcommand{\tendvers}[2]{\xrightarrow[#1\to#2]{}}$

I. Métro parisien et plus court chemin

Exercice 1

def monsplit(S):
    assert(" " in S)
    i = 0
    while S[i] != " ":
        i += 1
    A = S[:i]
    B = S[i + 1:]
    return A, B

monsplit('0001 Alexandre Dumas')

('0001', 'Alexandre Dumas')

Exercice 3

stations = {}

with open("stations.txt") as fichier_stations:
    for line in fichier_stations:
        line = line.strip()
        num, sommet = monsplit(line)
        stations[int(num)] = sommet
fichier_stations.close()

stations[0]

'Abbesses'

Exercice 4

N = len(stations)
M = [[float("inf") for j in range(N)] for i in range(N)]

with open("trajets.txt") as fichier_trajets:
    for line in fichier_trajets:
        line = line.strip()
        s1, s2, poids = line.split()
        M[int(s1)][int(s2)] = float(poids)
fichier_trajets.close()

M[1][12]

36.0

Exercice 5

Il suffit d'ajouter une variable predecesseur que l'on met à jour lorsque l'on trouve un trajet plus court :

def dijkstra(G, s0):
    N = len(G)
    predecesseur = [None for _ in range(N)]
    visite = [False for _ in range(N)]
    dist = [float('inf') for _ in range(N)]
    dist[s0] = 0
    for _ in range(N):
        mini = float('inf')
        for v in range(N):
            if not visite[v] and dist[v] <= mini:
                s, mini = v, dist[v]
        visite[s] = True
        for v in range(N):
            if not visite[v] and dist[v] > dist[s] + G[s][v]:
                predecesseur[v] = s
                dist[v] = dist[s] + G[s][v]
    return dist, predecesseur

Exercice 6

On remonte le trajet à partir de s1, prédécesseur par prédécesseur, jusqu'à obtenir s0 :

def trajet(G, s0, s1):
    dist, predecesseur = dijkstra(G, s0)
    trajet = [s1]
    while s1 != s0:
        s1 = predecesseur[s1]
        trajet.append(s1)
    return trajet[::-1] # le trajet est à l'envers sinon...

Exercice 7

On a besoin du dictionnaire "réciproque" de stations :

stations_r = {value : key for key,value in stations.items()}

stations_r["Opéra"]

225

Le plus court trajet "Opéra$\to$Pasteur" est alors obtenu de la manière suivante :

trajet(M, stations_r["Opéra"], stations_r["Pasteur"])

[225, 177, 79, 138, 158, 371, 156, 155, 45, 348, 232]

Si l'on souhaite le nom des stations lors de ce trajet :

T = trajet(M, stations_r["Opéra"], stations_r["Pasteur"])
print([stations[t] for t in T])

['Opéra', 'Madeleine', 'Concorde', 'Invalides', 'La Tour-Maubourg', 'École Militaire', 'La Motte Picquet, Grenelle', 'La Motte Picquet, Grenelle', 'Cambronne', 'Sèvres Lecourbe', 'Pasteur']

Exercice 8

def changement(T):
    chgmt = []
    for i in range(len(T)-1):
        if stations[T[i]] == stations[T[i+1]]:
            chgmt.append(stations[T[i]])
    return chgmt

changement(T)

['La Motte Picquet, Grenelle']

II. Coordonnées GPS et visualisation graphique

Exercice 9

import folium

%run gps.py

gps["Abbesses"]

(48.884392717043454, 2.338394635220906)

Exercice 10

def traGPS(T):
    return [gps[stations[t]] for t in T]

Pour le trajet "Opéra$\to$Pasteur", on obtient :

traGPS(T)

[(48.871437428049184, 2.3310472867112395),
 (48.87054467576818, 2.3258100487932767),
 (48.866557992001624, 2.3229614457982586),
 (48.86109201043299, 2.314632660444516),
 (48.85772702258638, 2.3104735359369832),
 (48.854919659638895, 2.3063456838200755),
 (48.8496308034842, 2.2985257262366354),
 (48.8496308034842, 2.2985257262366354),
 (48.84754311124529, 2.3029417283376103),
 (48.84564768170248, 2.3095296104303924),
 (48.842528386594964, 2.312914680473939)]

Exercice 11

T = trajet(M, stations_r["Opéra"], stations_r["Pasteur"])
trace = traGPS(T)
debut = trace[0]
fin = trace[-1]

paris = folium.Map(location = (48.85611450681713, 2.312155284838142), zoom_start = 12)
folium.Marker(location=debut, tooltip="Début", icon=folium.Icon(color="green")).add_to(paris)
folium.Marker(location=fin, tooltip="Fin", icon=folium.Icon(color="red")).add_to(paris)
folium.PolyLine(trace, tooltip="Trajet").add_to(paris)
paris.fit_bounds(paris.get_bounds(), padding=(50, 50))
paris.save('map.html')

En ouvrant le fichier map.html dans un navigateur, vous devriez voir la carte suivante :

paris

Make this Notebook Trusted to load map: File -> Trust Notebook

Exercice 12

def dijkstra(G, s0):
    N = len(G)
    predecesseur = [None for _ in range(N)]
    chemins_explores = []
    visite = [False for _ in range(N)]
    dist = [float('inf') for _ in range(N)]
    dist[s0] = 0
    for _ in range(N):
        mini = float('inf')
        for v in range(N):
            if not visite[v] and dist[v] <= mini:
                s, mini = v, dist[v]
        visite[s] = True
        for v in range(N):
            if not visite[v] and dist[v] > dist[s] + G[s][v]:
                chemins_explores.append([s,v])
                predecesseur[v] = s
                dist[v] = dist[s] + G[s][v]
    return dist, predecesseur, chemins_explores

def trajet(G, s0, s1):
    dist, predecesseur, chemins = dijkstra(G, s0)
    trajet = [s1]
    while s1 != s0:
        s1 = predecesseur[s1]
        trajet.append(s1)
    return trajet[::-1], chemins

T, C = trajet(M, stations_r["Opéra"], stations_r["Pasteur"])
trace = traGPS(T)
debut = trace[0]
fin = trace[-1]

paris = folium.Map(location = (48.85611450681713, 2.312155284838142), zoom_start = 12)
folium.Marker(location=debut, tooltip="Début", icon=folium.Icon(color="green")).add_to(paris)
folium.Marker(location=fin, tooltip="Fin", icon=folium.Icon(color="red")).add_to(paris)
for chemin in C:
    c = traGPS(chemin)
    folium.PolyLine(c, tooltip="Chemin explorés", color = "green").add_to(paris)
folium.PolyLine(trace, tooltip="Trajet", color = "red").add_to(paris)
paris.fit_bounds(paris.get_bounds(), padding=(50, 50))
paris.save('map.html')

paris

Make this Notebook Trusted to load map: File -> Trust Notebook