Algorithme de Dijkstra

Поделиться
HTML-код
  • Опубликовано: 12 дек 2024

Комментарии • 115

  • @Unlesslight
    @Unlesslight 4 года назад +28

    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...

  • @guyoteen6118
    @guyoteen6118 4 года назад +23

    Une vidéo de qualité qualitative !!!

  • @martindupouy9432
    @martindupouy9432 3 года назад +3

    Incroyablement incroyable !!!

  • @ett0rac438
    @ett0rac438 3 года назад +14

    C'est vraiment une vidéo TOP.

    • @lixray7592
      @lixray7592 3 года назад +2

      Grace à elle, j'ai mieux compris les graphes orientés et pondérés

    • @romsansanlag1667
      @romsansanlag1667 3 года назад +2

      Totalement d'accord on pourrait même l'utiliser pour un cours de NSI

  • @myscreen4256
    @myscreen4256 Год назад +1

    Tu expliques trop bien merci

  • @zarkha_
    @zarkha_ 4 года назад +3

    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 !

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  4 года назад +1

      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.

    • @zarkha_
      @zarkha_ 4 года назад

      @@a_la_decouverte_des_graphes je vous remercie je vais regarder ça ! ^^

    • @younescha2359
      @younescha2359 4 года назад

      c'est aussi interessant de voir sous forme de tableau ça serai une bonne interpretation

    • @abdelkaremhomidi7322
      @abdelkaremhomidi7322 Год назад

      @@a_la_decouverte_des_graphes le lien svp

  • @lolapaquay1130
    @lolapaquay1130 4 года назад +3

    Super vidéo, très propre, très claire, très bien expliquée !

  • @macdonalds6039
    @macdonalds6039 6 лет назад +6

    Merci j'ai rattrapage demain ta video est top !

  • @Totogas
    @Totogas 3 года назад +1

    VOUS ETES AU TOP ! JESPERE AVOIR PLUS DE VIDEO COMME CELLE CI QUI SONT DES CLASSIQUES ! MODERE LES GRAPHES PONDERE

  • @aminazarroug5473
    @aminazarroug5473 3 года назад +1

    J'aurais jamais cru comprendre cet algorithme aussi facilement ! Merci infiniment

  • @hadjer168
    @hadjer168 3 года назад +1

    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 !!!

  • @benjamindeporte3806
    @benjamindeporte3806 3 года назад

    Tellement clair... un vrai bonheur. Un grand merci.

  • @anishamak6002
    @anishamak6002 4 года назад +1

    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é

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  4 года назад

      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".

  • @juliengimenez2360
    @juliengimenez2360 3 года назад

    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.

  • @pierre-andreline5023
    @pierre-andreline5023 3 года назад

    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 ?

  • @rostanecherif3681
    @rostanecherif3681 6 лет назад +1

    Bonjour, comment peut on utiliser l'algorithme de djiksta avec une liste binaire?

  • @th3o77
    @th3o77 8 месяцев назад +2

    incroyable kakou kakou

  • @elasmarsaadallah6126
    @elasmarsaadallah6126 4 года назад +1

    Quel logiciel utilisez vous pour ces animations ?

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  4 года назад +1

      Vous trouverez sur ma chaine une vidéo qui explique tout cela : "Comment je fais mes vidéos avec Keynote"

  • @sawadogojanvier8857
    @sawadogojanvier8857 7 месяцев назад +1

    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

  • @PAUL-jh3zn
    @PAUL-jh3zn Год назад

    Je t'aime mon reuf
    ❤❤❤❤❤

  • @diallosadou3963
    @diallosadou3963 5 лет назад +1

    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

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  5 лет назад +2

      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.

    • @diallosadou3963
      @diallosadou3963 5 лет назад

      À la découverte des graphes merci pour la réponse cordialement

  • @ehouaiscestdwiouaiscestbie2528
    @ehouaiscestdwiouaiscestbie2528 Год назад +1

    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?

  • @naoufhlel1094
    @naoufhlel1094 2 года назад

    Super Vidéo ! Bravo a vous !

  • @anas.2k866
    @anas.2k866 5 лет назад

    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

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  5 лет назад

      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.

    • @anas.2k866
      @anas.2k866 5 лет назад

      @@a_la_decouverte_des_graphes Merci !

  • @louisrererer1708
    @louisrererer1708 5 лет назад

    je t'aime j'ai regardé toutes tes vidéos je suis ton plus grand fan, et vive la théorie des graphes

  • @adoteam
    @adoteam 5 лет назад +2

    Très bien expliqué, merci beaucoup !

  • @ayoubgouicem8250
    @ayoubgouicem8250 5 лет назад +1

    Je vous bien remercie pour cette bonne illustration.

  • @saghdaouieman2101
    @saghdaouieman2101 2 года назад

    Merci infiniment 💙
    Ms quand le chemin est unique ?

  • @happylife9397
    @happylife9397 4 года назад +1

    Merci monsieur 😁.

  • @zoubidafadelamalti5014
    @zoubidafadelamalti5014 5 лет назад

    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.

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  5 лет назад

      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.

    • @zoubidafadelamalti5014
      @zoubidafadelamalti5014 5 лет назад

      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.

    • @zoubidafadelamalti5014
      @zoubidafadelamalti5014 5 лет назад

      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.

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  5 лет назад

      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.

    • @zoubidafadelamalti5014
      @zoubidafadelamalti5014 5 лет назад

      ok merci

  • @shizotaiko1628
    @shizotaiko1628 Год назад

    bonjour
    si 'il vous plait mr j'arrive pas a comprendre l'utilite de kruskal si on utilse Djikstra

  • @elyan3695
    @elyan3695 3 года назад

    TROP BIEN LA VIDEO MERCI

  • @sihamelghazi5356
    @sihamelghazi5356 3 года назад

    Merci bcp pour l'explication

  • @maneltidjet4222
    @maneltidjet4222 Год назад

    💯💯💯💯

  • @_strawberry_212
    @_strawberry_212 3 года назад +1

    trop bien la videooo

  • @mathieu__9111
    @mathieu__9111 2 года назад +4

    ESSAYE DE FAIRE UN FT AVEC GOTAGA
    OU MICHOU

  • @MaxD1609Prod
    @MaxD1609Prod 4 года назад

    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

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  4 года назад +1

      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...

    • @MaxD1609Prod
      @MaxD1609Prod 4 года назад

      @@a_la_decouverte_des_graphes je vais regarder cela merci beaucoup

  • @amaldaagi5450
    @amaldaagi5450 4 года назад

    donne moi un algorithme approché de problème de satisfiabilité et merci

  • @recorr
    @recorr Год назад

    si b c était de 13, on resterait bloqué sur b ?
    (puisque 6+13 >18 ????)

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  Год назад

      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.

  • @JamesGT620
    @JamesGT620 3 года назад

    Incroyable

  • @naikoalonzo5230
    @naikoalonzo5230 Год назад

    Igo je n'ai pas compris. Peut tu refaire une vidéo en changeant ta voie. Igo merci

  • @leopoldbader3081
    @leopoldbader3081 5 лет назад +1

    Merci !!

  • @asmaeflory7683
    @asmaeflory7683 3 года назад

    TOP DU TOP❤ MERCI !

  • @toitespasmoi
    @toitespasmoi 4 года назад

    Qu'aurait-il arrivé sur le chemin entre D et B aurait été de 99? L'algorithme aurait été faux non..?

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  4 года назад

      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é".

    • @toitespasmoi
      @toitespasmoi 4 года назад

      @@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?

  • @DarrenMbono
    @DarrenMbono 10 месяцев назад

    Vamos!!

  • @baptisteuh544
    @baptisteuh544 3 года назад

    MERCI

  • @stevebambou8781
    @stevebambou8781 3 года назад

    Cool le cours

  • @anouarcanee8485
    @anouarcanee8485 5 лет назад +1

    J'aime les math pour moi c'est un jeu

  • @LeaderBear
    @LeaderBear 4 года назад

    Merci

  • @aminekoob5871
    @aminekoob5871 3 года назад +1

    Je me suis endormie en cour avec mes camarade si vous voulez passer votre année à dormir vous êtes au bonne endroit

  • @hugotboss7578
    @hugotboss7578 8 месяцев назад

    itinéraire pour aller sur le toit des maisons

  • @Romainsc_cars_bike
    @Romainsc_cars_bike 7 месяцев назад

    une video qui a les crampté

  • @BluZix
    @BluZix 2 года назад

    tu sauves mon semestre

  • @mazencore
    @mazencore 2 года назад

    merci !

  • @ramzirebouh2364
    @ramzirebouh2364 5 лет назад +1

    TAG NTIC تخلطت

  • @LamtoroS
    @LamtoroS 6 лет назад

    super

  • @benjicoor2.083
    @benjicoor2.083 2 года назад

    Suuuuuuuuuuuuuu

  • @SimonLeGac
    @SimonLeGac Год назад +4

    zbi comprend pas

  • @marwahero6843
    @marwahero6843 5 лет назад

    slt merci bien pour votre explication jaimrai bien vous nous explique l'alogorithme de dijkstra chemain poid maximal svp

  • @kimigrosdemange5756
    @kimigrosdemange5756 Год назад +1

    des informations de la sorte contribuent a accroitre ma capacité cérébrale

  • @quentingueganton8280
    @quentingueganton8280 3 года назад +1

    C'est abérant comment on s'instruit ici

  • @naoufhlel1094
    @naoufhlel1094 2 года назад +1

    Je n'ai pas aimé cette vidéo

  • @wave8748
    @wave8748 3 года назад

    JE HAIS LA SNT

  • @lebossleboss4249
    @lebossleboss4249 3 года назад +1

    Super video insta gus_dpls

    • @ma-row171
      @ma-row171 3 года назад +2

      Courage auustin

  • @alphaze_mrs7470
    @alphaze_mrs7470 8 месяцев назад +2

    la pire vidéo que j'ai vu jusqu'à aujourd'hui. Je n'ai littéralement rien compris.

  • @mathisnicolet286
    @mathisnicolet286 4 года назад +1

    Wah trop cool j'ai perdu 9minutes de ma vie merci

    • @a_la_decouverte_des_graphes
      @a_la_decouverte_des_graphes  4 года назад

      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.

    • @mathisnicolet286
      @mathisnicolet286 4 года назад

      À la découverte des graphes et merceeee le couzzz

    • @maisvoilamaiscetaitsurenfa6559
      @maisvoilamaiscetaitsurenfa6559 3 года назад

      eh merci a la découverte des graphes par contre Mathis lave tes oreilles

    • @maisvoilamaiscetaitsurenfa6559
      @maisvoilamaiscetaitsurenfa6559 3 года назад

      ta playlist nul

  • @mathieu__9111
    @mathieu__9111 2 года назад +2

    CA FLINGUE MON REUF WOLA

  • @aminekoob5871
    @aminekoob5871 3 года назад +1

    Vidéo très nul je déconseille fortement

  • @narkatato1095
    @narkatato1095 3 года назад +3

    cette vidéo est nul dsl mais elle ne ma rien appris juste j'ai perdu 9min de ma vie

  • @elodia_pers3206
    @elodia_pers3206 4 года назад

    merci

  • @rafiksalmi2826
    @rafiksalmi2826 Год назад

    merci