Bonjour, Nous sommes un groupe de trois en classe de Terminale S,en spécialité ISN. Pour notre projet de fin d’année,nous voulons réaliser un plan de métro dans lequel il est possible de rentrer la destination d’arrivée et de départ au choix. Il donne ensuite le chemin le plus court. Le graphe est non orienté. On a réussi à parcourir le graphe avec une destination et un point de départ FIXES. En revanche, on galère pour trouver un programme qui nous permet de choisir le départ et l’arrivée. Nous bloquons particulièrement car nous devons convertir le nom des stations en entiers, afin qu'ils puissent être traités dans la fonction "plus_court_chemin". Nous avons utilisés une table d'association pour cela mais cela ne fonctionne toujours pas. Avez vous une idée de pourquoi? Nous vous mettons ci-dessous notre code:



Code : Sélectionner tout - Visualiser dans une fenêtre à part
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)
Merci de votre aide!