$\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]{}}$
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')
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'
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
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
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...
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']
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']
import folium
%run gps.py
gps["Abbesses"]
(48.884392717043454, 2.338394635220906)
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)]
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
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