Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Algorithme de Dijkstra

Posté par
jpigrec
21-06-15 à 17:26

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.

Posté par
jeveuxbientaider
re : Algorithme de Dijkstra 21-06-15 à 17:35

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 !

Posté par
jpigrec
re : Algorithme de Dijkstra 21-06-15 à 19:29

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.

Posté par
jeveuxbientaider
re : Algorithme de Dijkstra 21-06-15 à 19:38

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 !

Posté par
sloreviv
re : Algorithme de Dijkstra 21-06-15 à 19:39

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

Posté par
jpigrec
re : Algorithme de Dijkstra 21-06-15 à 20:06

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.

Posté par
jpigrec
re : Algorithme de Dijkstra 21-06-15 à 20:11

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.

Posté par
jeveuxbientaider
re : Algorithme de Dijkstra 21-06-15 à 20:11

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 !

Posté par
jeveuxbientaider
re : Algorithme de Dijkstra 21-06-15 à 20:31

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 :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !