IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Parcours de graphe


Sujet :

Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Nouveau candidat au Club
    Homme Profil pro
    Lycéen
    Inscrit en
    Mai 2019
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Mai 2019
    Messages : 1
    Par défaut 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 : 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!

  2. #2
    Membre Expert

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Par défaut
    Citation Envoyé par Theo ISN 001 Voir le message
    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

  3. #3
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 835
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 835
    Billets dans le blog
    1
    Par défaut
    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 Voir le message
    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...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

Discussions similaires

  1. Parcours de graphe avec circuit
    Par aurelien.tournier dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 03/11/2006, 16h06
  2. Problème algo de parcour de graphe
    Par goblin dans le forum Langage
    Réponses: 1
    Dernier message: 11/12/2005, 15h04
  3. Algorithme de parcour de graphe :(
    Par scaleo dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 03/10/2005, 10h36

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo