Bonjour,
La fille d'un ami qui passe le bac ES m'a posé une question à laquelle je n'ai pas su répondre.
Il s'agit d'un exercice (simple) sur trouver le plus court chemin dans un graphe avec l'algorithme
de Dijkstra ; mais cet exercice (simple) présente une particularité qui est qu'à un moment on a deux
sommets de même poids.
Alors pour finir le traitement quel sommet faut-il choisir ? Et si on choisi l'un puis l'autre de ces
2 sommets alors les 2 chemins final auront-ils forcément le même poids ?
J'ai tenté d'insérer l'image du graphe en question mais je ne suis pas sûr d'avoir réussi (l'explication
sur le site m'a paru particulièrement obscure).
https://www.ilemaths.net/forum-attachement.php?numtopic=0
Merci d'avance.
Bonjour,
Alors tu conseilles à la fille de ton ami de passer par là elle comprendra peut-être comment envoyer une image , ici .
Ce n'est pas si compliqué que cela et assez bien expliqué dans la FAQ !
Sinon regarder la correction du sujet Bac ES Liban mai 2014 ! On prend n'importe quel sommet avec le même poids , si ce n'est pas le bon on trouvera bien la réponse plus tard !
Bonjour "jeveuxbientaider",
Merci de cette réponse .... complétement inutile car l'exemple Bac ES Liban 2014 ne correspond justement pas au cas particulier pour lequel je poste.
J'ai finalement vu comment insérer l'image mais elle est trop lourde et comme je n'ai que PAINT comme traitement d'image ce que je ne fais jamais (sauf cette exception) je ne peux pas la réduire le poids de cette image.
Ceci étant, on peut trouver cet exercice et son corrigé à l'adresse :
http://www.academie-en-ligne.fr/Ressources/7/MA04/AL7MA04TEPA0013-Sequence-03.pdf (page 7/43).
J'explique à nouveau le cas particulier de cet exercice :
->à la 2eme itération on trouve pour le sommet D le poids 40(B)
->à l'itération suivante (donc la 3eme) on fixe A et on trouve alors pour D le poids 40(A)
D'où la 1ère question : pour terminer l'exercice est-ce qu'il faut faire systématiquement les 2 choix possibles (comme c'est fait dans le corrigé)?
Et si oui est-ce que, d'un point de vue théorique, les 2 chemins différents ainsi identifiés (E-B-A-D-C-S et E-B-D-C-S) sont FORCEMENT, comme dans cet exercice, de même poids (60) ?
Merci d'avance.
Dans l'épreuve du liban 2014 au premier rang on trouve 2 pour A et C en venant de B ....
Qu'on choisisse A ou C on trouvera bien la bonne réponse , mais bon ....
Ton lien ne marche pas !
bonjour
je ne veux pas creer de pb
mais jpigrec tu prends celui des sommets de mm poids ( compilés) que tu veux et dans le deroulement tu seras oblige de reprendre l'autre apres une ligne de ton tableau
Bonjour "jeveuxbientaider",
1)Désolé mais j'ai lu trop rapidement et j'avais regardé le bac ES Liban 2013 et non 2014 que tu avais indiqué.
Là aussi on trouve donc encore 2 chemins différents de même poids (5): peut être que dans ce cas lorsqu'on trouve 2 chemins différents alors ils ont FORCEMENT le même poids (?).
Je n'ai pas assez de connaissances théoriques sur les graphes pour conclure mais la conjecture semble probable.
2)Concernant le lien je ne comprends pas : depuis le texte de mon post, si je fais copier/coller dans Internet Explorer 11 ou Firefox 38 ça marche (le lien s'arrête à .pdf, il ne faut pas prendre la parenthèse donnant le numéro de page).
Merci de ta participation.
Bonjour sloreviv,
Merci de ta réponse mais je ne vois pas pourquoi il y aurait création de problème.
Bonne fin de journée.
Ton lien comme le mien te montre que dans ce genre de situation , quel que soit le choix entre les 2 chemins équivalents tu vas trouver la bonne réponse !
Et pourquoi jpiunegrec tu nous fais croire que tu postes pour quelqu'un d'autre ?
Travailler seul(le) par le biais du CNED demande une énorme rigueur et une très grosse performance que peu de nos posteurs pourraient revendiquer !
Ne pas baisser les bras mais demain on pensera à toi quand on aura le sujet !
MERDE !
Ne réponds pas !
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :