Discussion:Algorithme de Dijkstra

Approche trop informatique

Me mettant à la place d'un programmeur qui ne connaîtrait pas cet algorithme, il y aurait de quoi m'induire en erreur sur la compréhension de l'algorithme car l'article dans sa forme actuelle n'est pas mathématiquement correcte. Poids(s1,s2) n'est normalement pas une procédure extérieure à $G$ mais une application qui fait partie du graphe. En réalité, l'algorithme ne peut être utilisé que sur des graphes valués, donc du genre : $G=(S,A,p)$ où $p$ est une application qui à chaque arête associe un entier naturel. Evidemment, l'utilisation d'une procédure Poids(s1,s2) peut être employée dans un programme, mais c'est une simple astuce de programmation selon moi.

il me semlait en effet que l'article partait trop vite sur une programmation (que je ne peux pas valider). J'ai donc déplacé l'exemple en l'expliquant davantage et présenter un tableau "construit à la main" qui devrait je pense éclairer sur la construction théorique de l'algorithme. Celui-ci en réalité ne donne pas seulement le plus crourt chemine de A vec B mais tous les plus courts chemins de A vers X (X variable). Comme je fais plus des maths que de l'informatique, n'hésitez pas à changer si vous estimez que je suis trop "à côté de la plaque". HB (d) 30 juin 2009 à 19:21 (CEST)

Orienté ou non orienté ?

Je crois que l'algo ne s'applique pas seulement aux graphes orientés si on considere qu'un graphe non orienté est un graphe orienté dans les 2 sens..

Effectivement, on peut utiliser l'algo pour les graphes orientés ou pas, tant qu'ils sont connexes. J'ai deja fais des exercices avec les 2 cas.--Paul Bouchequet 25 janvier 2007 à 20:41 (CET)

Notations

Vous penseriez pas qu'il faudrait utiliser des notations plus explicites genre noter l'ensemble des noeuds N au lieu de W? Franckyboy 29 mar 2005 à 00:58 (CEST)

Bah fais le ! C'est un wiki ! Tom 31 mar 2005 à 13:45 (CEST)

En général, on note N, en effet. FR 29 mai 2007 à 16:36 (CEST)

Euh, normalement, on les note V à cause de l'anglais "vertices". --213.41.243.33 (d) 30 avril 2012 à 10:59 (CEST)

Ensemble des sommets de départ ?

Quand j'ai étudié l'algorithme, dans le livre qui expliquait l'algorithme, ils ne parlaient pas d'un unique sommet origine, mais d'un ensemble de sommets d'origine.

À mon avis, cela dépend si les sommets définissant le plus court chemin cherché sont fixés. Peut-être que s'il y a de multiples sommets de départ dans ton livre, c'est parce qu'il s'agit d'une généralisation de l'algorithme pour tout sommet de départ et tout sommet d'arrivée. Après, ce n'est qu'une hypothèse. FR 29 mai 2007 à 16:35 (CEST)

orthographe

c'est bizarre, mais le nom des villes allemandes change au fur et a mesure (Mannheim perd un n, Augsburg gagne un f,...) et que veut dire "Dis" dans le "Code" ? MFH (d) 22 janvier 2008 à 07:45 (CET)

Erroné ?

J'ai beau tourner cela dans tous les sens, je ne vois pas comment l'algorithme peut fonctionner... il y a peut être une erreur de recopiage.

En effet, on prend successivement toutes les valeurs de Q et on les analyse ; le hic est que on ne peut modifier que la valeur du noeud en cours d'analyse s1 (peu importe le "si", la seule valeur que l'on se propose de modifier est "d[s1]"). Cela pourrait fonctionner si on ne supprimait pas s1 de Q.

Ainsi, dans l'exemple Frankfurt -> Munich, on analyserait une première fois "Munich" pour lui assigner la distance 675. Mais à ce moment, Munich est supprimé de Q. Il est donc impossible de remodifier la valeur de Munich pour y mettre 487 puisque le seul moyen de modifier une valeur est de l'analyser (le "mettre en s1").

L'erreur est évidente quand on regarde le début :

 Pour n parcourant nœuds
   n.parcouru = infini   // Peut être implémenté avec -1
   n.precedent = 0
 Fin pour
 debut.parcouru = 0
 PasEncoreVu = nœuds.enlever(debut)
 Tant que PasEncoreVu != liste vide
   n1 = minimum(PasEncoreVu)   // Le nœud dans PasEncoreVu avec parcouru le plus petit

Le problème est que PasEncoreVu ne contient que des noeuds de distance infinie, il est donc impossible de déterminer "minimum(PasEncoreVu)"

Proposition de correction

2 Q := ensemble de tous les nœuds /* on enlève "sauf sdeb" */

maj_distances(s1,s2)
1 si d[s2] > d[s1] + Poids(s1,s2)
2    alors d[s2] := d[s1] + Poids(s1,s2)
3         prédecesseur[s2] := s1          /* on fait passer le chemin par s1 */

Ainsi, au lieu de prendre tous les noeuds non analysés et de leur assigner une valeur à partir de la valeur du parent, on analyse les noeuds dont on connait déjà la valeur et on modifie la valeur des enfants

N'étant qu'en deuxième année, je ne suis pas sûr de moi ; merci de faire les modifications si vous pensez que j'ai raison :)

Je confirme, et l'article anglais est comme la version proposée Pierre KRIEGER (d) 19 avril 2008 à 09:54 (CEST)

Exemple à reprendre

Si l'exemple est juste mathématiquement parlant, il est faux dans la réalité : les distances entre ces villes ne sont pas celles qui sont indiquées. De plus, comme l'a déjà remarqué MFH, l'orthographe en est fluctuante. Cela mérite la création d'un nouvel exemple mais cela risque e prendre du temps. En attendant, exemple à manier avec précaution. HB (d) 1 juillet 2009 à 13:32 (CEST)

Nouvelle version mise en ligne. HB (d) 2 juillet 2009 à 13:30 (CEST)

Concours d'implémentations ?

En plus du pseudo-code, qui me semble suffisamment clair, je vois deux autres implémentations, en OCaml et en Python. Qu'est-ce que ça apporte ? Il me semble qu'elles auraient plus leur place sur RosettaCode. Ou alors c'est un appel au crime : pourquoi pas une implémentation en Scheme, Java, Pascal, Basic, Fortran, et j'en passe ? Elopash (d) 26 août 2011 à 11:03 (CEST)

C'est le même problème sur toutes les pages parlant d'algorithmes. RosettaCode, Wikibooks, il y a plein d'endroits pour mettre ceci. Zandr4^[Kupopo ?] 26 août 2011 à 12:29 (CEST)

J'ai vu ça. Je serais partant pour faire un peu de nettoyage... Est-ce qu'il y a une recommandation "officielle" au sujet des codes sources sur wp ? Elopash (d) 26 août 2011 à 13:34 (CEST)

Sur les codes sources ça m'étonnerait, mais peut-être que ça vaudrait le coup de lancer un bon troll sur le projet informatique :) Zandr4^[Kupopo ?] 26 août 2011 à 18:59 (CEST)

les poids doivent être des entiers naturels ?

ça marche pour tout poids réel positif, non ? (cf l'intro) Hector2 (d) 5 décembre 2012 à 17:24 (CET)

exact. La restriction aux entiers naturels ne se justifie pas, il suffit de restreindre les poids à des réels positifs ou nuls = > je modifie en ce sens. HB (d) 5 décembre 2012 à 18:11 (CET)

avantages/inconvénients

J'ai effectué quelques modifications, notamment dans la mise en forme. Cependant, j'ai aussi retiré le fait qu'un des avantages de l'algorithme est de pouvoir remplacer les distances par des coûts, car ce n'est pas propre à l'algorithme, mais à n'importe quel graphe, il suffit juste de bien définir son graphe : l'algorithme de Dijkstra ne sert qu'à par la suite répondre à un problème de type plus court chemin à origine unique sur ce graphe. Varmin^{Un problème?} 3 février 2013 à 14:51 (CET)

Cette section comporte des informations fausses. L'algorithme A* est une extension de l'algorithme de Dijkstra. Si l'heuristique choisie est admissible (si elle ne surestime pas le coût réel), A* retournera le chemin le plus court. C'est d'ailleurs pour ça qu'il s'appelle A* (l'étoile exprime l'optimalité). De plus, cette section ne me semble pas ajouter d'informations tellement pertinentes à part l'impossibilité d'avoir des poids négatifs.--195.221.233.130 (d) 30 juillet 2013 à 17:01 (CEST)

Complexité

Bonjour,

Dans la section « Améliorations de l’algorithme », j’ai récemment fait une modification brutale. Il était dit que l’utilisation d’un tas binomial permettait une complexité O((n+m)ln(n)) pour n nœuds et m arêtes, et j’ai affirmé péremptoirement qu’un tas binaire suffit. En effet, sauf erreur de ma part, les seules opérations de tas-min dont on a besoin sont la suppression du minimum et la diminution d’une clef, et toutes deux sont au pire en O(ln(n)) avec un tas binaire (on peut trouver en temps constant le nœud du tas et la clef associés à une valeur donnée, en implémentant le tas binaire avec un tableau et en maintenant à jour le tableau « inverse »). Comme on fait au plus une de ces deux opérations pour chaque nœud et pour chaque arête, on obtient bien la complexité annoncée. Cependant, je n’ai pas de source à avancer, il est donc possible que je me trompe. Qu’en pensez-vous ?

Par ailleurs, la complexité de l’algorithme ne mériterait-elle pas d’être au moins évoquée dans l’introduction de l’article ? Il me semble qu’il s’agit d’une des premières informations qui intéresse un lecteur.

— Maëlan (discuter) 9 janvier 2015 à 15:02 (CET)

Approche structure de données

Il s'agit de construire progressivement un chemin vu comme une liste de sommets. Cet algorithme se prête bien à une description récursive. Au départ, on considère une liste vide de listes vides (i.e. un ensemble vide de chemins). La première étape consiste donc à créer autant de listes que le sommet de départ possède de voisins immédiats. Ces listes sont triées selon la distance de leur tête au sommet de départ. A chaque étape, une et une seule liste est mise à jour par adjonction d'une tête à laquelle est associée la distance à l'origine par simple addition. A chaque étape, la première liste représente le chemin le plus court. L'étape suivante consiste à ajouter à la tête de l'une de ces listes le sommet accessible (successeur) qui minimisera la longueur des chemins. La liste mise à jour devient la première des listes. Si le plus petit successeur de la première liste produit un chemin plus long que le second, c'est celui-ci que l'on tente de prolonger. Et ainsi de suite jusqu'à ce que l'on trouve le prolongement qui minimise la distance à l'origine résultante. Si le successeur ajouté figure en tête d'une autre liste, cette dernière peut être supprimée. L'algorithme s'arrête quand le sommet destination est ajouté comme tête de l'une des listes.

L'implémentation peut être réalisée au moyen d'un tableau et d'une liste. Le tableau permet de stocker le détail de chaque chemin ; la liste est composé de structures indiquant la distance à l'origine et le nombre de sommet du chemin. La liste est triée par distance minimale à l'origine. Le reste de l'implémentation va de soi. --Xavoux (discuter) 27 mars 2015 à 15:10 (CET)

Refonte

Bonjour à tous,

Une journée wikipedia a été organisée à Rennes. En tant qu'enseignant-chercheur, nous avons restructuré un petit peu l'article. Nous espérons que nous avons amélioré l'article. Nous sommes ouverts à la discussion.

Merci et bonne journée.--Fschwarzentruber (discuter) 10 décembre 2015 à 16:17 (CET)

L'exemple

Bonjour, je trouve que l'exemple induit une mise en page bizarre. Qu'en pensez-vous ? Est-ce que l'on pourrait avoir une sorte de boite unique, où l'on ferait défiler les différentes étapes clic par clic ? --Roll-Morton (discuter) 7 mars 2017 à 18:40 (CET)

En fait il me semble que la vidéo qui est en tête d'article est mieux que notre exemple image par image, qu'en pensez-vous ? --Roll-Morton (discuter) 13 mars 2017 à 09:42 (CET)

Probablement mieux pour quelqu'un qui connait déjà le fonctionnement de l'algorithme mais une animation sans commentaire n'a aucun sens pour qui découvre l'algorithme. Je préférais ton idée de boite unique cliquable permettant de suivre les étapes une à une. HB (discuter) 13 mars 2017 à 09:48 (CET)

Bonne remarque sur les commentaires, et merci pour l'avis sur la boite. Je vais voir si c'est réalisable. --Roll-Morton (discuter) 13 mars 2017 à 10:00 (CET)

j'ai trouvé le modèle animation. Qu'en penses-tu ?HB (discuter) 13 mars 2017 à 10:26 (CET)

ça me parait être exactement ce qu'il nous faut ! --Roll-Morton (discuter) 13 mars 2017 à 18:05 (CET)

Et je n'avais pas vu la mise en place, très bien, merci ! A centrer peut-être ? Ou pas... --Roll-Morton (discuter) 13 mars 2017 à 18:07 (CET)

Pour répondre à la fin de la réponse de Fschwarzentruber (d · c · b) dans la discussion précédente : je ne suis pas très favorable à un exemple orienté ; certes l'algorithme marche dans le cas orienté, mais je ne suis pas sûr que ce soit le cadre le plus courant pour l'explication, et il est plus difficile à concevoir (on perd l'intuition première des réseaux routiers). --Roll-Morton (discuter) 31 mars 2017 à 15:04 (CEST)

OK Laissons l'exemple comme cela dans ce cas. On peut imaginer un graphe orienté qui vient d'un réseau routier avec des sens uniques. Mais c'est confus/lourdingue à expliquer (on est sensé expliquer Dijkstra pas la modélisation et les subtilités de sens unique dans un réseau routier ;) ). --Fschwarzentruber (discuter) 31 mars 2017 à 17:13 (CEST)

Implémentation

La partie implémentation ne me plaît pas beaucoup : elle ressemble plus à une recette de cuisine pour programmeur qu'à un contenu encyclopédique. J'exagère un peu, dans le sens où l'on ne donne pas un code prêt à compiler, mais tout de même je trouve que l'on rentre trop dans le détail, et qu'on pourrait imaginer d'autres implémentations, et qu'enfin l'algorithme lui-même est plus "haut niveau" que l'explication de l'initialisation etc. Qu'en pensez-vous ?--Roll-Morton (discuter) 13 mars 2017 à 18:20 (CET)

Là je serais plus prudente. En tant que matheuse, j'ai tendance à considérer les implémentations comme des recettes de cuisine. Mais ce n'est peut-être pas ce qu'en pense un informaticien. Je me méfie donc toujours de mon propre biais culturel quand j'ai tendance à enlever un contenu qui ne me semble pas encyclopédique. J'aimerais donc d'autres avis (par exemple auprès du projet:informatique). HB (discuter) 13 mars 2017 à 18:37 (CET)

Je trouve que la partie implémentation est trop détaillée et ne présente pas assez le "vrai" algorithme. L'algorithme Dijkstra, normalement, utilise une file de priorité. C'est bien présenté dans Algorithms de Papadimitriou et al. (désolé de faire de la publicité pour ce livre, il est plus simple que le Cormen). Un jour, je vais modifier "Schéma d'algorithme" pour le présenter comme cela. Sinon, je suis agréablement surpris par l'exemple ː c'est super la jolie animation. Par contre, désolé, mais... ça me gêne un peu que le graphe de l'exemple soit non orienté alors que Dijkstra fonctionne sur les graphes orientés (et donc non-orientés certes, mais c'est un cas particulier). --Fschwarzentruber (discuter) 14 mars 2017 à 00:39 (CET)

Je ne comprends pas trop la différence entre le pseudo-code de la section Schéma d'algorithme et celui de la section Implémentation. Si la différence est simplement l'ajout de commentaire, c'est mineur je trouve, autant fusionner les deux. Pour moi une implémentation c'est une vraie mise en œuvre de l'algorithme dans un langage concret, et je ne suis pas sûr que ça soit nécessaire sur un article encyclopédique (sauf s'il y a un intérêt sourcé, bien entendu). Quasar (discuter) 4 avril 2017 à 20:12 (CEST)

 QuasarFr, HB et Fschwarzentruber : Je pense qu'il y a plus que les commentaires : c'est du pseudo-code plus détaillé, par exemple, 'comment trouver la distance minimum' n'est pas expliqué dans la section schéma, mais l'est dans la section implémentation. A mon avis c'est inutile (parce qu'il est probablement impossible de comprendre l'algorithme si on n'a pas idée de la façon de trouver le minimum) et contre-productif (parce que ça rajoute plein de ligne et fait croire que l'algorithme est très compliqué). Je pense que le mieux est de pointer vers Algorithme de sélection, pour un éventuel lecteur qui aurait commencer l'algorithmique par là par hasard, et que l'on peut développer. --Roll-Morton (discuter) 27 avril 2017 à 11:20 (CEST)

Le problème c'est que personne n'implémente Dijkstra comme cela. Trouve_min(Q) donné dans l'article wikipedia est linéaire en le nombre de nœuds. Il faut utiliser une structure de données efficace ǃ --Fschwarzentruber (discuter) 27 avril 2017 à 11:23 (CEST)

Hum, le problème est plus profond qu'il n'y parait c'est vrai. Il faudrait jeter un coup d’œil aux livres pour savoir comment ils présentent la chose. Je serais tenté de dire que l'algorithme de Dijkstra est très haut niveau, avec juste l'idée de la programmation dynamique, et que la gestion des structures est de l'ordre des améliorations, ou même de l'implémentation, au sens large du terme. --Roll-Morton (discuter) 27 avril 2017 à 11:28 (CEST)

Tout à fait d'accord. Il ne faut parler de type abstrait (file de priorité) et structures de données (tas, tas de Fibonacci) tout de suite. C'est très bien que la majeur partie de l'article soit compréhensible par tous. Mais vers la fin de l'article, dans une section "Implémentation" ça me paraît naturel d'aller vers des concepts de niveau licence en informatique voire plus. Bonne journée.--Fschwarzentruber (discuter) 27 avril 2017 à 12:56 (CEST)

Poids ou distance ?

L’algorithme de Dijkstra calcule la plus courte distance, or dans sa description, on met des poids sur les arcs. On parle ainsi du poids d'un chemin, ce qui est pour le moins original ! Il y a clairement une incohérence de terminologie. --Pierre de Lyon (discuter) 30 janvier 2019 à 10:32 (CET)

Euh, je ne comprends pas bien ton objection : on utilise ce qu'on appelle en théorie des graphes un graphe pondéré dont les sommets sont les villes et dont les poids des arcs sont les distances entre deux villes. On parle donc bien de poids d'un arc et de distance entre deux villes. Que l'on parle ensuite de «poids du chemin» dans le schema algorithmique ne me choque pas même si, comme toi, j'aurais préféré parler de «distance du chemin». HB (discuter) 30 janvier 2019 à 10:58 (CET)

Dans [Dasgupta et al. Algorithms p. 121], ils parlent de "longueur d'un arc" et de calcul de "distances". Dans [Cormen et al., p. 679], ils parlent de "poids" et de "graphes pondérés", noeud le plus "léger" ou le "proche" (p. 122), chemin le plus "court". Je pense qu'il faut mentionner toutes les terminologies utilisées dans les sources. Puis continuer le reste de l'article avec l'une ou l'autre. J'ai une préférence pour la terminologie de [Dasgupta et al. Algorithms p. 121], plus concret. --Fschwarzentruber (discuter) 30 janvier 2019 à 11:09 (CET)

 HB : Qui est ce « on » ? Je ne parle pas de sources, je parle de didactique. Oui, je suis choqué par « poids d'un chemin ». Ne nous étonnons pas si certains lecteurs trouvent que nous jargonisons. --Pierre de Lyon (discuter) 30 janvier 2019 à 11:42 (CET)

Ah si on a le droit de se passer du terme de graphe pondéré et de celui de poids des arcs, comme le montre la source Dasgupta et al. , il est certain que c'est plus didactique et moins jargonnant de ne parler que de longueur. Faites... faites...HB (discuter) 30 janvier 2019 à 17:25 (CET)