Annuler
connectez vous
autre en post-bac
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann AutreTopics traitant de autre [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
algorithme de dijstra
Posté par jackobenco
Bonsoir à la communauté ,
Je suis bloqué dans un exercice d'optimisation dont le but est de trouver le chemin le plus de A à Z , il y a 26 sommets qui sont les lettres de l'alphabet.
Grâce à l'algorithme de dijstra , j'ai pu obtenir les 'poids' minimum qui permettent de passer A à (Si ) un sommet quelconque.
Tel que on obtient E=[A(0),D(1),B(2),E(3),H(3),C(4),I(4),G(5),J(5),M(7),N(7),0(8),L(9),F(10),R(11),K(12),Q(13),P(15),U(15),V(17),T(18),W(18),X(18),S(19),Y(21),Z(21)]
Les nombres entre parenthèses représentent le poids minimal qui de permet de passer de A à un sommet quelconque . B(2) : le passage de A vers B peut se faire avec un poids égal à 2.
Cependant grâce à cet algorithme , hormis le poids , je ne sais pas comment faire pour trouver le chemin permettant d'obtenir le poids minimal juste en regardant mon ensemble E.
Savez-vous comment je peux le faire juste en me servant de ce que j'ai obtenu ?
Merci d'avance
Cordialement ,
Bonjour !
Et pourquoi ne pas respecter les noms propres en les écrivant correctement, avec une majuscule ?
Edgser Wybe Dijkstra mérite, me semble-t-il, cette politesse.
Bonjour ,
oui j'évoque bien l'algorithme de Dijstra.
Savez vous comment je peux retrouver le chemin ?
merci d´avance
Lorsque tu mets à jour les distances, tu gardes le nœud par lequel tu passes (prédécesseur).
Une fois toutes les distances calculées pour reconstruire le chemin tu pars du sommet de fin (Z) et tu remonte les prédécesseurs jusqu'à tomber sur le sommet de départ (A).
bonjour,
justement comment déterminer par lequel noeud je passe ？
mon ensemble E ne me donne pas ce noeud.
lorsque je déroule l'algorithme à la main comment faire pour me repérer ？
merci d'avance
Bonjour,
Non il n'est pas dans l'ensemble c'est une information supplémentaire qu'il faut conserver pendant l'exécution.
Quel algorithme utilises-tu exactement? l'opération s'appelle en général mise à jour des distances ou relâchement.
cf wiki 
Sur feuille , j'exécute le programme comme cela (cf ton lien wiki):
Entrées : G = (S,A) un graphe avec une pondération positive poids des arcs , Sdeb un sommet S.
P= 
d[a]=+
pour chaque sommet de a .
d(Sdeb)=0
Tant qu'il existe un sommet hors de P
Choisir un sommet a hors de P de plus petite distance d[a]
Mettre a dans P
Pour chaque sommet b hors de P voisin de a
d[b]=min(d[b],d[a]+poids(a,b))
Fin Pour
Fin Tant Que
En fait , je ne fais qu'exécuter et donc ma "liste" P avec donc leur poids minimal associé.
Dans ce cas là , comment pendant le programme je peux retrouver mon noeud ?
Merci d'avance
Çà devrais ressembler à
P=
d[a]=+ pour chaque sommet de a .
prédécesseur[a] = NIL pour tout a
d(Sdeb)=0
Tant qu'il existe un sommet hors de P
Choisir un sommet a hors de P de plus petite distance d[a]
Mettre a dans P
Pour chaque sommet b hors de P voisin de a
si d[a] + poids(a,b) > d[b] :
d[b]=d[a]+poids(a,b)
prédécesseur[b] = a
Fin Pour
Fin Tant Que
Ensuite tu reconstruis le chemin en partant de la fin et en parcourant prédécesseur.