algortithme de Dijksra amérque du nord 28 mai 2019

[Cédric]

Bonjour,
dans l'algorithme de Dijksra (je vous laisse voir le sujet initial d'amérique du nord mai 2019), un moment dans l'algorithme, on a le choix entre 180(B) ou 180(L).
En prenant contrairement à eux, 180(L), l'algorithme bloque. Est-ce normal ?
Comment savoir quelles valeurs de quelle colonne choisir quand les valeurs sont identiques comme ici ?
Merci !
C.

[sos-math(21)]

Bonjour,
lorsque deux sommets ont la même pondération dans l'algorithme de Dijkstra, le choix de l'un ou de l'autre importe peu.
Dans le cas où l'on fait un choix de V(180) à la place de G(180), on sélectionne V et on regarde ses sommets adjacents :
- L est déjà traité donc on n'y revient pas
- le sommet G qui aurait alors une pondération de 180+90=270>180 donc on garde la pondération de 180 existante en G
- le sommet P qui aurait une pondération de 180+100>230 donc on garde la pondération existante de 230 venant de E
À l'issue de ce traitement, on regarde la plus faible pondération et on a le sommet G qui est à 180 que l'on traite et qui nous emmène vers P(230) puis vers C(260) puis vers A(410.
Au final, on reconstitue le même plus court chemin BLEPA avec un cumul de 410 : l'ordre de traitement inversé entre V et G ne change rien.
Bonne continuation

[Cédric]

Merci, tout est clair !!!
C.