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]
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]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Le principe est que si un chemin était meilleur en passant par D, tu y passerais avant de passer par F.
-- Schnoebelen, Philippe
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.
En supposant 4, mon algorithme trouve BCTN de longueur 23 et en supposant 5, il trouve BCTN de longueur 24.
-- Schnoebelen, Philippe
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.
-- Schnoebelen, Philippe
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.
-- Schnoebelen, Philippe
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. ça plante en fin d'algorithme, je ne comprends pas le message d'erreur.
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.
-- Schnoebelen, Philippe
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.