1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| Nvilles = 13
# A B C D E F G H I J K L M
S0408 = [0,0,0,0,0.66,0.85,0.45,0.42,0.8,0,0.48,0.32,0] #Monparnasse Bienvenue
S1510 = [0,0,0,0,0,0,0,0,0,0,0.39,0.5,0] #Raspail
S0207 = [0,0,0.36,0,0,0,0,0,0,0.66,0,0,0] #Duroc
S0208 = [0,0.5,0,0,0.36,0,0,0,0,0,0,0,0] #Vaneau
S0209 = [0.5,0,0.5,0.33,0,0,0,0,0,0,0,0,0] #Sèvres Babylone
S0211 = [0,0.33,0,0,0,0.43,0,0,0,0,0,0,0] #Rennes
S0412 = [0,0,0,0,0,0,0,0,0,0.42,0,0,0] #Saint Placide
S0414 = [0,0,0,0.43,0,0,0,0,0,0.85,0,0,0] #Notre Dame des Champs
S1601 = [0,0,0,0,0,0,0,0,0.42,0.45,0,0,0] #Falguière
S1602 = [0,0,0,0,0,0,0.42,0,0,0.8,0,0,0] #Pasteur
S0407 = [0,0,0,0,0,0,0,0,0,0.48,0,0,0.39] #Vavin
S0406 = [0,0,0,0,0,0,0,0,0,0.32,0,0,0.5] #Edgar Quinet
S0210 = [0,0.5,0,0,0,0,0,0,0,0,0,0,0] #Rue du Bac
m_adjac = [S0408,S1510,S0207,S0208,S0209,S0211,S0412,S0414,S1601,S1602,S0407,S0406,S0210]
conversion = {'S0408':0,'S1510':1,'S0207':2,'S0208':3,'S0209':4,'S0211':5,'S0412':6,'S0414':7,'S1601':8,'S1602':9,'S0407':10,'S0406':11,'S0210':13}
start_ville = input("ville de départ ? [oblitération]: ")
end_ville = input("ville d'arrivée ? [oblitération] : ")
m_adjac = [conversion.values()]
def plus_court_chemin(m_adjac,start_ville,end_ville = Nvilles-1):
DIJ = list() # la liste DIJ mémorise les données du tableau (cf. étape 1)
for i in range(Nvilles):
DIJ.append([float("inf"), "X", "N"]) # voir commentaire page suivante
ville_select = start_ville #numéro de la ville sélectionnée; 0 = ville de départ
dist_interm = 0 #distance pour arriver à la ville sélectionnée; 0 au départ
while ville_select != end_ville:
DIJ[ville_select][0] = dist_interm
DIJ[ville_select][2] = "O"
minimum = float("inf")
for n in range(0, Nvilles):
if DIJ[n][2] == "N":
dist = m_adjac[ville_select][n]
dist_totale = dist_interm + dist
print(ville_select, n, dist_totale)
if dist != 0 and dist_totale < DIJ[n][0]:
DIJ[n][0] = dist_totale
DIJ[n][1] = ville_select
if DIJ[n][0] < minimum:
minimum = DIJ[n][0]
pville_select = n
ville_select = pville_select # pville_select = numéro de la prochaine ville sélectionnée
dist_interm = minimum
ville = end_ville
chemin = [end_ville]
while ville != start_ville:
ville = DIJ[ville][1]
chemin.append(ville)
return(chemin)
print(chemin)
plus_court_chemin(m_adjac,start_ville,end_ville) |
Partager