Merci beaucoup monsieur, j'étais entrain de réviser d'un PDF qu'on m'a fournit de la part de mon prof. Mais c'est tellement nul que je suis venu ici pour comprendre. Merci beaucoup monsieur votre explication très compréhensible.
Bonjour, est ce qu'il ya un critere pour choisir l'ordre de relachement ?? car si je prond un autre ordre je trouverais un resultat different que le votre ??
Je ne comprend pas le premier exemple vous dites que c'est un graphe orienté pondéré sauf que dans les ressources que j'ai trouvé un graphe est dit pondéré quand chaque arrête poccéde des valeurs positif hors ici des valeurs sont négatives. Merci :)
Pondéré veut dire que le graphe a des poids/valeurs sur les arcs ou les sommets. Ces valeurs peuvent être positives ou pas. Cela va dépendre du contexte ou de l'application.
Bonsoir, j'aimerais être sûr d'avoir bien compris. Aucun algorithme ne permet de calculer justement le plus court chemin d'un graphe comprenant un circuit absorbant. C'est bien ça ? En fin de compte je ne comprend pas la différence entre Dijkstra et Bellman, puisque le test pour vérifier qu'il existe un cycle absorbant est applicable sur les 2 algorithmes. Si le graphe est composé d'un cycle absorbant, les 2 algorithmes s'arrêteront avec cette condition qui sera fausse. Pour résumer ce que j'ai compris: Ni Bellman, ni Dijkstra ne peuvent traiter des graphes avec des cycles négatifs (absorbant). Dijkstra peut traiter certains graphes avec poids négatifs (sans cycble absorbant) correctement, mais pas tous. Bellman peut traiter tous les graphes avec poids négatifs (sans cycle absorbant).
Non, n’utilisez pas Dijkstra si vous avez des poids négatifs, le résultat peut ne pas être correct comme je l’ai montré dans la vidéo précédente. Si le graphe contient un circuit absorbant accessible à partir du point de départ r il n’y a aucun chemin fini de poids le plus petit fini de r vers un sommet de ce circuit puisqu’en faisant ‘’un tour de plus’’ le poids décroît. Heureusement la présence d’un tel circuit peut être détectée grâce à l’algorithme de Bellman Ford décrit dans cette vidéo... Bref, si vous avez des poids négatifs, méfiez vous et utilisez l’algorithme de cette vidéo. Dans une prochaine vidéo je traiterai d’un cas particulier ou le lourd algorithme de Bellman Ford peut être remplacé par un plus léger. Il faut que je trouve le temps de l’enregistrer...
Bonjour, très bonne vidéo, vos explications sont très claires. J'ai cependant une question: en prenant comme ordre de relâchement des arcs (r,a) (a,b) (bc) (c,r) (c,a) j'obtiens une valeur de 4 au lieu de 5 pour le sommet c et une valeur de 0 pour le sommet a. Cela est il correct ?
Je n'ai pas eu le courage de refaire l'exécution avec votre ordre de relâchement. Mais cela ne serait pas surprenant que l'on obtienne ce que vous dites car, avec votre ordre, le relâchement de l'arc (c,a) a "un effet de plus" que dans mon ordre (lors de ma 1ère tournée de relâchements cet arc ne produit rien de nouveau, alors qu'avec votre ordre oui). Le point important c'est qu'à la fin il y ait bien un arc qui viole la condition et qui indique qu'il y a un circuit de poids négatif ce qui indique que vos résultats, comme les miens peuvent être "mis à la poubelle" car non "cohérents"...
bonjour j'ai une question si on a dans une arc une valeur positife et on a trouve une nouvella valeur dans le mémé arc mais cette valeur est négatif , quelle est la valeur que nous prenons ??puis si on a trouve la mémé valeur dans une arc mais avec 2 somment différent par exp: a->c et b->c ?? et merci ^^
Je n'ai pas compris la 1ère partie de la question. Un arc ne peut avoir qu'une seule valuer, qui ne change pas pendant le déroulement de l'algorithme. Pour la 2ème partie, je ne comprends pas.
Je n'ai pas refais les calculs avec votre ordre. Mais si ce que vous obtenez à la fin est bon, à savoir b=2, c=4 alors dans ce cas, c'est l'arc (c, a) qui viole la condition exprimée à la fin car on a alors 0=d[c] + w(c, a) < d[a] = 1. Il y a toujours un arc qui viole la condition, même si ce n'est pas le même qu'avec mon ordre.
Merci beaucoup monsieur, j'étais entrain de réviser d'un PDF qu'on m'a fournit de la part de mon prof. Mais c'est tellement nul que je suis venu ici pour comprendre. Merci beaucoup monsieur votre explication très compréhensible.
Vous méritez un prix Nobel, MERCI!!!
très bonne façon d'apprendre le Bell man Ford les explications sont incroyable. Merci !
Bon bah notre examen s'est bien passé merci pour vos super explications!
super bien, même pour ceux qui ne sont pas français, c'est super illustré et facile à suivre, merci!!!
merci beaucoup pour vos videos ,vous m'avez rendu un grand service
tip top, bien expliqué, bien illustré, parfait pour mes révisions!
Vraiment vous êtes au top du top , bonne continuation
Merci beaucoup monsieur
Incroyable vidéo encore
Grâce à vous j'ai réussi ma première interview ! On va voir ce que ça donne !
Bonjour, est ce qu'il ya un critere pour choisir l'ordre de relachement ?? car si je prond un autre ordre je trouverais un resultat different que le votre ??
très bien expliqué, merci
Merci beaucoup! Avez vous une vidéo sur algorithme de tarjan
Merci beaucoup شكرا
je vous remercie un question comment on a su l'order de relachement
c'est arbitraire
Je ne comprend pas le premier exemple vous dites que c'est un graphe orienté pondéré sauf que dans les ressources que j'ai trouvé un graphe est dit pondéré quand chaque arrête poccéde des valeurs positif hors ici des valeurs sont négatives.
Merci :)
Pondéré veut dire que le graphe a des poids/valeurs sur les arcs ou les sommets. Ces valeurs peuvent être positives ou pas. Cela va dépendre du contexte ou de l'application.
Bonjour, très bonne vidéo. Allez vous faire une vidéo sur le problème du flot maximum de coût minimum ?
Ce n’est pas prévu. Difficile à vulgariser...
Bonne chance pour MAG !
C'est qui/quoi MAG ?
Méthode Algorithmique et Graphe, on a un exam demain matin
(Licence 3 Informatique à Rennes)
Comment avez vous découvert ma chaîne ?
En cherchant des explications sur kosaraju :)
Bonsoir, j'aimerais être sûr d'avoir bien compris.
Aucun algorithme ne permet de calculer justement le plus court chemin d'un graphe comprenant un circuit absorbant. C'est bien ça ?
En fin de compte je ne comprend pas la différence entre Dijkstra et Bellman, puisque le test pour vérifier qu'il existe un cycle absorbant est applicable sur les 2 algorithmes. Si le graphe est composé d'un cycle absorbant, les 2 algorithmes s'arrêteront avec cette condition qui sera fausse.
Pour résumer ce que j'ai compris:
Ni Bellman, ni Dijkstra ne peuvent traiter des graphes avec des cycles négatifs (absorbant).
Dijkstra peut traiter certains graphes avec poids négatifs (sans cycble absorbant) correctement, mais pas tous.
Bellman peut traiter tous les graphes avec poids négatifs (sans cycle absorbant).
Non, n’utilisez pas Dijkstra si vous avez des poids négatifs, le résultat peut ne pas être correct comme je l’ai montré dans la vidéo précédente.
Si le graphe contient un circuit absorbant accessible à partir du point de départ r il n’y a aucun chemin fini de poids le plus petit fini de r vers un sommet de ce circuit puisqu’en faisant ‘’un tour de plus’’ le poids décroît. Heureusement la présence d’un tel circuit peut être détectée grâce à l’algorithme de Bellman Ford décrit dans cette vidéo...
Bref, si vous avez des poids négatifs, méfiez vous et utilisez l’algorithme de cette vidéo. Dans une prochaine vidéo je traiterai d’un cas particulier ou le lourd algorithme de Bellman Ford peut être remplacé par un plus léger. Il faut que je trouve le temps de l’enregistrer...
@@a_la_decouverte_des_graphes Entendu, merci de votre réponse ! Bon courage pour vos prochaines vidéos, elles sont d'une grande aide. :)
Bonjour, très bonne vidéo, vos explications sont très claires. J'ai cependant une question: en prenant comme ordre de relâchement des arcs (r,a) (a,b) (bc) (c,r) (c,a) j'obtiens une valeur de 4 au lieu de 5 pour le sommet c et une valeur de 0 pour le sommet a. Cela est il correct ?
Je n'ai pas eu le courage de refaire l'exécution avec votre ordre de relâchement. Mais cela ne serait pas surprenant que l'on obtienne ce que vous dites car, avec votre ordre, le relâchement de l'arc (c,a) a "un effet de plus" que dans mon ordre (lors de ma 1ère tournée de relâchements cet arc ne produit rien de nouveau, alors qu'avec votre ordre oui). Le point important c'est qu'à la fin il y ait bien un arc qui viole la condition et qui indique qu'il y a un circuit de poids négatif ce qui indique que vos résultats, comme les miens peuvent être "mis à la poubelle" car non "cohérents"...
@@a_la_decouverte_des_graphes Merci pour vos explications
🥇🥇♥️
bonjour j'ai une question si on a dans une arc une valeur positife et on a trouve une nouvella valeur dans le mémé arc mais cette valeur est négatif , quelle est la valeur que nous prenons ??puis si on a trouve la mémé valeur dans une arc mais avec 2 somment différent par exp: a->c et b->c ??
et merci ^^
Je n'ai pas compris la 1ère partie de la question. Un arc ne peut avoir qu'une seule valuer, qui ne change pas pendant le déroulement de l'algorithme.
Pour la 2ème partie, je ne comprends pas.
@@a_la_decouverte_des_graphes est ce que je peux envoyer un exercice et tu donnez la solution ?
Non, je ne fais pas ça.
Super vidéo je peux avoir de vidéo sur Algorithme de Floyd Warshall
Merci infiniment
j'ai pris cet ordre (r,a) (a,b) (b,c) (c,a) (c,r) mais j'ai pas trouver le meme resultat , derniere iteration j'ai eu b=2,c=4, a=1
Je n'ai pas refais les calculs avec votre ordre. Mais si ce que vous obtenez à la fin est bon, à savoir b=2, c=4 alors dans ce cas, c'est l'arc (c, a) qui viole la condition exprimée à la fin car on a alors 0=d[c] + w(c, a) < d[a] = 1. Il y a toujours un arc qui viole la condition, même si ce n'est pas le même qu'avec mon ordre.
Merci !