Projet ISN Terminale Demande d'aide

Parcours de graphe / plan de métro

ache a marqué ce sujet comme résolu.

Tout dépend de comment tu veux faire ton code.

Ici, tu sembles vouloir utiliser m_adj[0][0] == Distance entre S0408 et S0408.

Alors du coup ce code fera l’affaire :

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 = conversion[input("ville de départ ? [oblitération]: ")]
end_ville = conversion[input("ville d'arrivée ? [oblitération] : ")]

# m_adjac = [conversion.values()]

Du coup, ton code semble marcher.

Si tu veux utiliser S['S0408']['S0406'] == Distance entre S0408 et S0406 Alors, ce code te donnera la matrice d’adjacence :

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 = {0: 'S0408', 1: 'S1510', 2: 'S0207', 3: 'S0208', 4: 'S0209', 5: 'S0211', 6: 'S0412', 7: 'S0414',
              8: 'S1601', 9: 'S1602', 10: 'S0407', 11: 'S0406', 12: 'S0210'}

start_ville = input("ville de départ ? [oblitération]: ")
end_ville = input("ville d'arrivée ? [oblitération] : ")

madj = {conversion[i]:{conversion[j]:dist for j, dist in enumerate(ligne)} for i, ligne in enumerate(m_adjac)}

"""
    >>> madj['S0408']['S0209']
    0.66
"""

Mais il faudra alors adapter la fonction plus_court_chemin pour qu’elle utilise les même conventions.

+0 -0

Bonjour à tous, Je reviens après un long moment pour vous remerciez de toute l’aide que vous avez pu me fournir jusque là et je ne pense pas que j’aurais pu avancer aussi bien sans vous. Le programme, après avoir fait une petite modification sur une ligne de code, fonctionne! Donc je vous le mets juste en-dessous pour que vous le consultiez si vous voulez. Merci à toute la communauté ZdS!

Nvilles = 13

#   A B C D E F G H I J K L M
S0408 = [0,0,0.66,0,0,0,0.42,0.85,0.45,0.8,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.66,0,0,0.36,0,0,0,0,0,0,0,0,0] #Duroc
S0208 = [0,0,0.36,0,0.5,0,0,0,0,0,0,0,0] #Vaneau
S0209 = [0,0,0,0.5,0,0.33,0,0,0,0,0,0,0.5] #Sèvres Babylone
S0211 = [0,0,0,0,0.33,0,0,0.43,0,0,0,0,0] #Rennes
S0412 = [0.42,0,0,0,0,0,0,0,0,0,0,0,0] #Saint Placide
S0414 = [0.85,0,0,0,0,0.43,0,0,0,0,0,0,0] #Notre Dame des Champs
S1601 = [0.45,0,0,0,0,0,0,0,0,0.42,0,0,0] #Falguière
S1602 = [0.8,0,0,0,0,0,0,0,0.42,0,0,0,0] #Pasteur
S0407 = [0.48,0.39,0,0,0,0,0,0,0,0,0,0,0] #Vavin
S0406 = [0.32,0.5,0,0,0,0,0,0,0,0,0,0,0] #Edgar Quinet
S0210 = [0,0,0,0,0.5,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]

stations = {'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':12}

start_ville = input("ville de départ ? [oblitération]: ")
end_ville = input("ville d'arrivée ? [oblitération] : ")

NumVilleDepart = stations[start_ville] # on déclare un dictionnaire
NumVilleDest = stations[end_ville]

def plus_court_chemin(m_adjac,NumVilleDepart,NumVilleDest = 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 = NumVilleDepart  #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 != NumVilleDest:
      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 = NumVilleDest
  chemin = [NumVilleDest]
  while ville != NumVilleDepart:
      ville = DIJ[ville][1]
      chemin.append(ville)

  print ("plus court chemin, à lire à l'envers : ",chemin)

  print ("distance totale : ",DIJ[pville_select][0])

plus_court_chemin(m_adjac,NumVilleDepart,NumVilleDest)
+2 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte