Discuter:Algorithme de Dijkstra

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Informatique
 Algorithme de Dijkstra fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
Bon début Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?)
WikiProjet Mathématiques
 Algorithme de Dijkstra fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
Bon début Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet.

Sommaire

[modifier] 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.

[modifier] 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)

[modifier] 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)

[modifier] 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)

[modifier] 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)

[modifier] 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)