Parcours de graphe

Version imprimable

Parcours de graphe

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:

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!

05/05/2019, 20h34
lg_53

Citation:

Envoyé par Theo ISN 001

Nous avons utilisés une table d'association pour cela mais cela ne fonctionne toujours pas.

Ca veut dire quoi ça fonctionne pas ?Cela ne nous renseigne pas, il faut être plus précis. Vous avez un message d'erreur ? Ou bien le programme tourne mais ca ne fournit pas le résultat attendu ? Si vous avez une erreur, mettez la ici. Et si ce n'est pas le résultat attendu dites ce que vous avez demandé comme test, ce que ca produit et ce à quoi vous vous attendriez
05/05/2019, 22h32
Sve@r

Bonsoir

Déjà une remarque rapide: quoi qu'il arrive, le print(chemin) de la ligne 63 ne sera jamais exécuté.

Sinon ce projet semble un peu confusément écrit (trop de commentaires je pense !!!). Par exemple que représente "S0408" "S1510" et etc ? Des lignes de métro ? Pourquoi alors Falguière et Pasteur (ligne 12) sont dans des items différents ? Comment gérez-vous le fait qu'une station (ex Montparnasse) appartienne à plusieurs lignes de métro (4, 12, 13 et certainement d'autres) ? Que représentent ces chiffres "48", "32" et etc ?

Citation:

Envoyé par Theo ISN 001

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

Je ne vois même pas cette table dans le code (enfin pour moi ce serait une table qui dirait "duroc=123"). Mais quoi qu'il arrive, je ne pense même pas que ce soit nécessaire. Le plus court chemin se calcule entre A et B sans forcément que "A" et "B" soient des entiers. Faut simplement qu'ils puissent être positionnés dans le plan/la matrice...