Algorithme de Dijkstra
Вставка
- Опубліковано 3 жов 2024
- Algorithme de Dijkstra pour calculer les distances à partir d'un sommet dans un graphe pondéré. Cette vidéo illustre les principales étapes, sur un graphe orienté.
Cet algorithme est plus général que le parcours en largeur qui ne traite lui que de graphes non pondérés. - Наука та технологія
Une vidéo de qualité qualitative !!!
C'est vraiment une vidéo TOP.
Grace à elle, j'ai mieux compris les graphes orientés et pondérés
Totalement d'accord on pourrait même l'utiliser pour un cours de NSI
Super vidéo !
J'ajoute qu'il aurait été intéressant de faire le tableau de la trace, pour montrer les racines et les poids, comment les noter etc etc...
Incroyablement incroyable !!!
VOUS ETES AU TOP ! JESPERE AVOIR PLUS DE VIDEO COMME CELLE CI QUI SONT DES CLASSIQUES ! MODERE LES GRAPHES PONDERE
Merci beaucoup ! Je ne connaissais pas cette algo et je suis tomber sur la meilleur vidéo qui traite du sujet, parfait pour de la prog ! ^^ Dommage que vous ne montrez pas un exemple plus compliqué, mais sa ma quand meme beaucoup aidé ! Bonne continuation et je m'abonne !
Merci. Il y a une autre vidéo plus détaillée sur le même sujet sur ma chaîne. Elle devrait mieux vous convenir.
@@a_la_decouverte_des_graphes je vous remercie je vais regarder ça ! ^^
c'est aussi interessant de voir sous forme de tableau ça serai une bonne interpretation
@@a_la_decouverte_des_graphes le lien svp
Tu expliques trop bien merci
J'aurais jamais cru comprendre cet algorithme aussi facilement ! Merci infiniment
Merci j'ai rattrapage demain ta video est top !
Merci ! J'espère que le rattrapage a été OK.
Super vidéo, très propre, très claire, très bien expliquée !
Bonjour monsieur, en esperant que vous vous portez bien.
Je vous joins ce commentaire afin de vous demander comment retrouver un circuit absorbant dans un graphe en utilisant l'algorithme de Dijkstra.
Merci pour vos vidéos de qualité
Bonjour.
Pour détecter les circuits de poids négatifs je vous invite à regarder ma vidéo : "Algorithme de Bellman Ford et les poids négatifs".
je t'aime j'ai regardé toutes tes vidéos je suis ton plus grand fan, et vive la théorie des graphes
Tellement clair... un vrai bonheur. Un grand merci.
incroyable kakou kakou
Super Vidéo ! Bravo a vous !
Formidable!!!
SVP j'ai une question, si on arrive au sommet C qu'on a pas encore découvert tous les autres sommets (parce que je suis partie de e) est-ce que je continue la découverte ? Car je vois que le sommet C n'a pas un arc sortant mais un arc entrant !!!
Très bien expliqué, merci beaucoup !
Bonjour, il y a quelque chose que j'ai du mal à comprendre. L'algo de Dijkstra n'est pas fait pour les graphes cycliques
les arêtes AE, EB, BA ne rendent-elle pas le graphe cyclique?
Pourquoi dites-vous qu’il n’est pas fait pour les graphes cycliques ?
@@a_la_decouverte_des_graphes je pense que j'ai mal interprété ce que j'ai lu , désolé et merci :)
Je vous bien remercie pour cette bonne illustration.
TROP BIEN LA VIDEO MERCI
Je t'aime mon reuf
❤❤❤❤❤
trop bien la videooo
Merci monsieur 😁.
Bonjour. D'un point de vue de l'implémentation, ce qu'on appelle relâchement ici serait juste le changement de père ( dans un tableau pere) pour un sommet ?
On ne garde au final que le père de chemin plus court.
Merci bcp pour l'explication
Si l'on suit le raisonnement pour déterminer le chemin le plus court de 'd' vers 'a', on aboutit à une impasse en 'c'. De manière générale, comment traiter un sommet en impasse (qui n'a pas de chemin orienté vers un autre sommet) lorsque ce sommet a une étiquette plus petite que les autres depuis le sommet précédent ?
Vous allez programmer l’algorithme de Dijkstra pour le calcul des plus courts
chemins a aux moins 10 villes (chef lieu de provinces) du BURKINA FASO.
Description du Projet :
▶ Impl´ementer l’algorithme de Dijkstra pour calculer les chemins les plus courts
entre diff´erentes villes.
▶ Utiliser des donn´ees de distances entre les villes pour construire un graphe
pond´er´e.
▶ Afficher les chemins les plus courts entre une ville de d´epart et toutes les autres
villes.
Je demande une aide avec cet exemple
Demande d'aide svp !
Bonjour, est ce qu’on peut avoir une vidéo aussi pour l’algorithme de bell man ford et la notion de flaux max svp , sinon le reste est impeccable
diallo sadou. J’ai traité Les flots Max dans trois vidéos sur ma chaîne. Regardez les pour voir si cela correspond à ce que vous cherchez.
À la découverte des graphes merci pour la réponse cordialement
Merci infiniment 💙
Ms quand le chemin est unique ?
Incroyable
Bonjour, comment peut on utiliser l'algorithme de djiksta avec une liste binaire?
Je ne comprends pas votre question...
Quel logiciel utilisez vous pour ces animations ?
Vous trouverez sur ma chaine une vidéo qui explique tout cela : "Comment je fais mes vidéos avec Keynote"
si b c était de 13, on resterait bloqué sur b ?
(puisque 6+13 >18 ????)
On ne reste "bloqué" nulle part avec cet algonquins. Je vous invite à refaire le déroulement de l'algo. avec la valeur que vous proposez. Vous verrez alors que lors de l'examen (relâchement) de l'arc b,c avec votre valeur de 13, le parent de c ne changerait tout simplement pas.
💯💯💯💯
bonjour
si 'il vous plait mr j'arrive pas a comprendre l'utilite de kruskal si on utilse Djikstra
Ce sont deux algorithmes qui n’ont pas le même objectif.
@@a_la_decouverte_des_graphes ahh ouii d'accord ,merci
Merci !!
TOP DU TOP❤ MERCI !
Igo je n'ai pas compris. Peut tu refaire une vidéo en changeant ta voie. Igo merci
donne moi un algorithme approché de problème de satisfiabilité et merci
Une erreur dans le graphe N1. Le sens de la fleche de b vers c et non pas de c vers v. J'ai trouvé enn appliquant Djikistra 10 = a-e-d-b-c. C'est un exemple tres simple. Pouvez vous nos proposer des graphes orientés plus compliqués que l'on puisse s'exercer. Merci par avance.
Je ne comprends pas votre remarque : il n'y a pas de sommet v dans le schéma. Si vous parlez du sommet b alors l'arc est bien orienté de b vers c et pas de c vers b dans l'exemple qui sert de support à l'exécution de Dijkstra. C'est un choix. Attention, ce n'est pas le même graphe que dans la 1ère partie de la vidéo.
Le chemin orienté a-> e -> d -> b ->c que vous évoquez est bien de poids 10, ce que trouve l'algorithme et c'est ce qui est dans la vidéo.
Je ne pense pas proposer d'exemples plus gros, c'est un peu plus dur à faire en vidéo et ça serait ennuyeux à suivre pour les auditeurs. Ma volonté est de faire des vidéos courtes qui montrent l'essentiel.
Vous avez raison l'exemple proposé est simple mais c'est voulu.
Regardez à la minute 1:42 mn dans le premier graphe en haut à gauche, le sens du chemin de c vers b est orienté vers le bas(arc c-->b de poids =4. A la minute 1:46 ce même arc est de sens contraire. Il est de bas en haut b-->c de poids = 4. L'exercice est pris en compte suivant cette dernière orientation de de b-->c. J'ai donc fait comme vous l'exercice suivant cette orientation et j'ai trouvé 10 comme vous.
Quand vous exposez tous les graphes ensemble pour expliquer les differents chemins possibles, l'arc cb est dirigé de c-->b. Quand vous commencez l'exercice, le premier graphe est seul et l'ac est de b vers c, b-->c.
Oui, mais comme je vous le disait, je sais que ce n'est PAS le même graphe entre 1:42 et 1:46, c'est fait intentionnellement. D'ailleurs l'arc entre b et c n'est pas la seule différence entre les deux j'ai aussi ajouté l'arc de b vers a (b->a) qui est dans le 2ème graphe mais n'est pas présent dans le 1er graphe.
Le 1er graphe sert à illustrer le fait qu'un plus court chemin pondéré n'est pas forcement un chemin avec le plus petit nombre d'arcs.
Le 2ème graphe, différent du premier, sert à illustrer l'algorithme de Dijkstra.
Vous n'avez pas vu la transition entre les deux parties mais c'est vrai que j'aurais du la marquer plus nettement.
ok merci
Cool le cours
Bonjour ! Si à la place de 10 il y avait 3 on aurait deux chemin qui pointent vers le meme sommet et qui ont la meme distance, dans cette situation on garde quel chemin ? Merci d'avance
anas .2k. Si au début d’une étape deux sommets non encore traités ont la même distance minimale alors il faut en choisir un, n’importe lequel. Ceci dit dans l’exemple que vous proposez lorsque l’algorithme arrive en e il relâcherait les deux arcs dont celui avec le poids 3 vers b. Lorsque l’arc d,b sera examiné plus tard cela ne permettra plus de modifier la distance pour venir en b. Le père de b serait alors e dans ce cas de figure.
@@a_la_decouverte_des_graphes Merci !
Vamos!!
MERCI
merci
tu sauves mon semestre
Qu'aurait-il arrivé sur le chemin entre D et B aurait été de 99? L'algorithme aurait été faux non..?
Je ne comprends pas votre question.
Si le poids de l'arc (D,B) avait été de 99 alors l'algorithme n'aurait pas sélectionné cet arc au moment où le sommet D est "examiné".
@@a_la_decouverte_des_graphes Merci de la réponse, mais comme il n'y a qu'un chemin vers D>B et que E>D a été choisi car il était de valeur 2 versus 10, l'algorythme va nécessairement prendre ce unique chemin vers B non?
Merci
merci !
merci
Salut ! J'ai vraiment du mal a trouver un algorithme pouvant résoudre mon problème mais je suis certain qu'il existe : j'ai besoin d'un algo qui me trouve le plus court chemin peu importe le sommet de départ mais qui passe par tous les sommets (une ou plusieurs fois peu importe). Si quelqu'un sait m'aider ça serait génial ! Très bonne vidéo au passage
Bonjour.
Ce n'est pas étonnant que vous ne trouviez pas car ce que vous demandez est (lié au) connu sous le nom du problème du chemin hamiltonien, qui est un problème NP-complet (actuellement personne ne connait d'algorithme efficace pour résoudre de tels problèmes et il est conjecturé qu'il n'en existe pas). Je vous invite à regarder la vidéo de ma chaine consacrée au problème du cycle hamiltonien (quasiment la même chose).
Bon courage...
@@a_la_decouverte_des_graphes je vais regarder cela merci beaucoup
une video qui a les crampté
itinéraire pour aller sur le toit des maisons
J'aime les math pour moi c'est un jeu
Alors amusez-vous bien!
Suuuuuuuuuuuuuu
slt merci bien pour votre explication jaimrai bien vous nous explique l'alogorithme de dijkstra chemain poid maximal svp
super
Merci !
ESSAYE DE FAIRE UN FT AVEC GOTAGA
OU MICHOU
TAG NTIC تخلطت
zbi comprend pas
Force
des informations de la sorte contribuent a accroitre ma capacité cérébrale
JE HAIS LA SNT
C'est abérant comment on s'instruit ici
Je me suis endormie en cour avec mes camarade si vous voulez passer votre année à dormir vous êtes au bonne endroit
Je n'ai pas aimé cette vidéo
la pire vidéo que j'ai vu jusqu'à aujourd'hui. Je n'ai littéralement rien compris.
Super video insta gus_dpls
Courage auustin
Wah trop cool j'ai perdu 9minutes de ma vie merci
Voilà une critique constructive ! Vous pouvez être plus explicite ? Je vous signale, pour information, qu’il y a une autre vidéo sur ma chaîne qui traite du même sujet et qui vous conviendrait peut-être plus.
À la découverte des graphes et merceeee le couzzz
eh merci a la découverte des graphes par contre Mathis lave tes oreilles
ta playlist nul
CA FLINGUE MON REUF WOLA
Vidéo très nul je déconseille fortement
cette vidéo est nul dsl mais elle ne ma rien appris juste j'ai perdu 9min de ma vie
tg
@@lebossleboss4249 mec tu vas te faire bann je donne mon avis c tout
@@narkatato1095 blc de ton avis