Algorithme de Dijkstra — Les-mathematiques.net The most powerful custom community solution in the world

Algorithme de Dijkstra

Bonjour
Je m'interroge à propos de l'exercice 1 question 4 page 1.
On applique l'algorithme de [large]D[/large]ijkstra.
On cherche la plus courte chaîne de B à N.
La première étape de l'algorithme sélectionne le sommet C car 12<15.
La deuxième étape sélectionne le sommet D car la chaîne BCD a un poids inférieure aux chaînes BCT, BCF, BF.

Ma question est : si FN avait un poids de 1 alors BFN aurait un poids de 16 et donc la plus courte chaîne ne serait pas BCTN (poids de 23) mais BFN. Or l'algorithme nous fait choisir le sommet D.
Il y a quelque chose que je ne comprends pas.
Pouvez-vous m'éclairer ?
Merci.

[Edsger Wybe Dijkstra (1930-2002) prend toujours une majuscule. AD]

Réponses

  • L’algorithme fait chercher de proche en proche la longueur du plus court chemin de chaque sommet du graphe au sommet B jusqu’à épuisement des points accessibles à partir de B.
    Le principe est que si un chemin était meilleur en passant par D, tu y passerais avant de passer par F.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Il me semble qu'il y a une erreur dans la correction (page 5 du document joint) :
    A l'étape quatre, le sommet actif devrait être (il me semble) le sommet F. En effet, à l'étape précédente on voit qu'en passant par D, F coûte 19 mais il ne faut pas oublier qu'en passant par B, F coûte 15. Si on oublie cela, alors dans le cas où l'arrête FN coûte 1, on ne trouve pas le chemin le plus court BFN.
    A l'étape 5, on se rend compte que T coûte 16 en passant par C ou 23 en passant par F puis N coûte 23 en passant pas F ou 26 en passant par D. On choisit donc le sommet T en passant par C. Ce qui nous donne le chemin BCTN. Mais si FN coûtait 1 alors en ayant choisi F à l'étape 4, on aurait vu que N coûtait 16 en passant par F et T aurait coûtait 16 en passant par C. Mais N étant le point d'arrivée, aurait eu fini. Et obtenu le chemin BFN.
  • As-tu écrit un programme qui le fait ? De C à T, c’est 4 ou 5 ?
    En supposant 4, mon algorithme trouve BCTN de longueur 23 et en supposant 5, il trouve BCTN de longueur 24.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • B
    F
    C
    T
    D
    N
    15B
    12B
    15B/15C
    16C
    14C
    15B/19D
    16C/17D
    26D
    16C/23F
    26D/38F
    26D/23T
    Donc le chemin le plus court est BCTN.
    La ligne "15B/19D 16C/17D 26D" me fait choisir le point F.
    Dans la correction on ne calcule jamais les distances à partir du point F.
  • C’est une erreur, le point F est le quatrième utilisé (si tu commences par B).
    def dijkstra():
    
     P=print
     M={"B":{"C":12,"F":15},
        "C":{"B":12,"D":2,"F":3,"T":5},
        "D":{"C":2,"F":4,"T":3,"N":12},
        "F":{"B":15,"C":3,"D":4,"T":8,"N":23},
        "N":{"D":12,"F":23,"T":7},
        "T":{"C":5,"D":3,"F":8,"N":7}}
    
     d=input("Depart ")
     a=input("Arrivee ")
    
     inf=float("inf")
     p={s:"None" for s in M}
     D={s:inf for s in M}
     D[d]=0
     f=set(M)
    
     while f:
      smin=min(f,key=lambda s:D[ s])
      f-={smin}
      P("choix "+smin+" "+str(D[smin])+
              " venant de "+p[smin].replace("None","nulle part"))
      for s in f:
       if s in M[smin] and D[smin]+M[smin][ s]<D[ s]:
        D[ s]=D[smin]+M[smin][ s]
        p[ s]=smin
    
     s=a
     pc=[ s]
     while s!=d:
      s=p[ s]
      pc=[ s]+pc
    
     P(D[a])
     P("-".join(pc))
    

    bb8d47793c524e72fa07e7f231cb73dc.png
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Merci pour l'algorithme.
    Il est écrit en python ?
    Je ne m'y connais pas en python mais j''ai installé le logiciel sur mon ordinateur.
    Je n'arrive pas à exécuter le programme.
    Je l'ai copié puis collé dans IDLE puis enregistré sous le nom Dijkstra. L'extension est .py
    Je vois dans le programme "d=input("Depart ")
    a=input("Arrivee ")" mais quand je veux poser d=B, on me renvoit que B n'est pas défini.
    Encore une fois je ne m'y connais pas du tout.
  • Pose d="B" et a="N", ça marchera mieux.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Oui effectivement B et N sont des chaînes de caractères...
    J'ai appliqué l'algorithme de Dijkstra pour l'exercice bac ES 2018 métropole DijkstraExo3Q3 exercice 3 question 3. Comme précédemment dans la correction correctionPage3, un point est oublié, ici c'est le point A. J'ai appliqué l'algorithme pour vérifier. L'algorithme passe également par A. Donc il y a un souci avec la correction. Pourtant c'est une correction du site APMEP. Ca me laisse perplexe.
    def dijkstra():
    
     P=print
     M={"D":{"B":40,"H":19,"A":28},
        "B":{"F":14},
        "H":{"B":16,"A":26,"F":32},
        "A":{"B":12,"F":25},
        }
    
     d=input("Depart ")
     a=input("Arrivee ")
    
     inf=float("inf")
     p={s:"None" for s in M}
     D={s:inf for s in M}
     D[d]=0
     f=set(M)
    
     while f:
      smin=min(f,key=lambda s:D[ s])
      f-={smin}
      P("choix "+smin+" "+str(D[smin])+
              " venant de "+p[smin].replace("None","nulle part"))
      for s in f:
       if s in M[smin] and D[smin]+M[smin][ s]<D[ s]:
        D[ s]=D[smin]+M[smin][ s]
        p[ s]=smin
    
     s=a
     pc=[ s]
     while s!=d:
      s=p[ s]
      pc=[ s]+pc
    
     P(D[a])
     P("-".join(pc))
    
    >>> dijkstra()
    Depart D
    Arrivee F
    choix D 0 venant de nulle part
    choix H 19 venant de D
    choix A 28 venant de D
    choix B 35 venant de H
    Traceback (most recent call last):
    File "<pyshell#10>", line 1, in <module>
    dijkstra()
    File "<pyshell#9>", line 32, in dijkstra
    s=p[ s]
    KeyError: 'F'
    ça plante en fin d'algorithme, je ne comprends pas le message d'erreur.
  • Bulledesavon:

    Sur un graphe issu d'une épreuve de bac TES, il n'est pas difficile de calculer à la main la longueur d'un chemin donné.

    Si tu as un chemin valide qui est plus court que le chemin proposé comme le plus court, tu sais qu'il y a un problème avec la solution proposée. B-)-

    Par ailleurs, un chemin le plus court n'est pas nécessairement unique.
  • Dans le corrigé de l'apmep on applique l'algorithme de Dijkstra. Je trouve le même chemin que celui de la correction mais dans l'application de l'algorithme, on doit utiliser un point, le point A, qui n'est pas utilisé dans la correction.
  • Ajoute ça dans ta liste d’adjacence :
       "F":{}
    
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Dans la correction de l'apmep, je pense que c'est une erreur d'étourderie.
    Dernière colonne deuxième ligne c'est A(28) et non D(28).
    Du coup dans la troisième ligne c'est 40A au lieu de 68D.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!