Explication Dijkstra

[Anna.stasia]

Bonjour,
J'ai besoin d'aide pour comprendre Dijkstra, rien que le nom ça annonce déjà la complexité du truc...
Bref je me débrouillais pas trop mal jusqu'à ce que je tombe sur l'exercice sur ce thème dans le bac du Liban, parfois les arêtes ont le même ordre et du coup comment choisir ?
J'arrive pas à mettre une photo de l'exercice alors je vous met le lien du sujet entier, c'est l'exercice 3 question 5 : [/IMG] file:///C:/Users/portable/Desktop/www.math93.com%20images%20pdf%20annales_bac%20Bac_ES%20bac_es_2014%20Bac_ES_2014_Liban-Math93.pdf.png

Il faut déterminer le temps minimal, mais déjà dès le départ on a 2 choix soit passer au point A soit au C mais l'ordre des arrêtes est 2 dans les 2 cas... Ca m'énerve tellement 1h que je suis dessus ^^
Merci d'avance

[Cliffe]

rien que le nom ça annonce déjà la complexité du truc...

:dodo: :doh: :triste: :mur: :bad:

[MacManus]

Voici le sujet en question: pdf

Tu dois chercher le plus court chemin pour aller du sommet H au sommet B.
Tu affectes le poids 0 au sommet H et les poids de tous les autres sommets par
Ensuite tu analyses les arrêtes de plus faible poids pour passer d'un sommet à un autre... etc en actualisant les poids à chaque étape par ordre croissant (càd sans oublier de prendre en compte le poids des arêtes précédentes).

C'est un résumé un peu grossier de l'algorithme de Dijsktra, mais l'idée est là !

[Anna.stasia]

Merci, mais je ne comprend pas comment choisir le chemins le plus court avec le tableau qu'on nous oblige à faire pour faire marcher cet algorithme.
Je m'explique : Ca commence dès le départ du premier sommet comment pour aller de B à A et de B à C c'est le même temps. Donc ensuite il faut faire deux parcours différent, mais on retombe à nouveaux sur 2 trajectoire différentes mais de même temps (en partant de C pour aller à E par exemple).
Or dans nos exercices en classe à chaque fois on notait dans un tableaux le temps et on supprimait ceux qui étaient les plus élevés et il nous restait ainsi qu'un seul temps.

Pourquoi à chaque fois les exos en cours sont plus facile et ne nous font pas apprendre/comprendre ce qu'on va réellement nous demander à l'examens...
PS: excusez moi si je suis pas claire, mais le corrigé m'a plus embrouillée qu'autre chose...

[MacManus]

Ce n'est pas grave si deux arêtes présentent la même valeur, ce qui compte, c'est de parcourir tous les sommets en un temps minimum en partant d'un sommet quelconque (ici B) pour arriver jusqu'à H.

le plus court chemin pour aller de:
B à A, c'est 2
B à C, c'est 2
B à D, c'est 2+1=3
B à E, c'est 2+1=3
B à F, c'est 2+1+1=4
B à H, c'est 2+1+1+1=5

[Anna.stasia]

Excusez moi de ne pas avoir répondu plus tot. Mais j'ai vue votre message avant le Bac, et ça m'a aidé a comprendre j'ai réussi à faire l'exo du sujet de Liban. En revanche il n'y avait pas d'exercice sur Dijkstra au Bac, tant pis si jamais je devait en faire un au cours de ma vie, je saurais désormais :)
Merci pour votre réponse !