Algorithme de Dikjstra : Différence entre versions
De Sciencinfolycee
m (Remplacement du texte — « 1.4. Algorithmes classiques » par « Algorithmes classiques ») |
|||
(4 révisions intermédiaires par 2 utilisateurs non affichées) | |||
Ligne 5 : | Ligne 5 : | ||
|SiloRole=auteur; | |SiloRole=auteur; | ||
|SiloLangue=fre | |SiloLangue=fre | ||
− | |Résumé=Présentation de l'algorithme de Dikjstra. | + | |Résumé=Présentation de l'algorithme de Dikjstra, publié en 1959 par son inventeur, l'informaticien néerlandais Edsger Dijkstra : il sert en théorie des graphes à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Il s'applique à un graphe connexe dont le poids lié aux arêtes est positif ou nul. En théorie de la complexité, on démontre que cet algorithme est polynomial. |
− | |Catégorie=Algorithmes classiques | + | |Catégorie=Algorithmes classiques |
− | |Mots-clés contrôlés=algorithme classique; algorithme de la théorie des graphes; problème du plus court chemin; algorithme de Dijkstra; | + | |Mots-clés contrôlés=algorithme classique; algorithme de la théorie des graphes; problème du plus court chemin; algorithme de Dijkstra; théorie de la complexité des algorithmes; Dijkstra, Edsger : 1930-2002; |
|SiloTypeDocumentaire=texte | |SiloTypeDocumentaire=texte | ||
|SiloTypologieGenerale=article | |SiloTypologieGenerale=article | ||
Ligne 13 : | Ligne 13 : | ||
|SiloStructure=atomique | |SiloStructure=atomique | ||
|SiloNiveauAgregation=1.Le plus petit niveau (grain) | |SiloNiveauAgregation=1.Le plus petit niveau (grain) | ||
− | |Format= | + | |Format=PDF |
|SiloTypePedagogique=cours / présentation | |SiloTypePedagogique=cours / présentation | ||
|SiloPublicCible=enseignant | |SiloPublicCible=enseignant | ||
|SiloRelation=est une partie de | |SiloRelation=est une partie de | ||
|SiloRelationURL=http://www.irisa.fr/celtique/pichardie/teaching/L3/ALGO/ | |SiloRelationURL=http://www.irisa.fr/celtique/pichardie/teaching/L3/ALGO/ | ||
− | |Evaluateur=Thierry ; Diane Rives (indexation);MG | + | |Evaluateur=Thierry ; Diane Rives (indexation); MG; DB |
|Statut d'évaluation=publiée | |Statut d'évaluation=publiée | ||
|SiloNote=Bla | |SiloNote=Bla | ||
}} | }} |
Version actuelle datée du 17 février 2012 à 16:04
Section Description | |
---|---|
URL | http://www.irisa.fr/celtique/pichardie/teaching/L3/ALGO/dikjstra.pdf |
Titre | Algorithme de Dikjstra |
Auteur(s) | Pichardie, David |
Fonction(s) | auteur |
Notes | |
Section Analyse | |
Langue | fre |
Résumé | Présentation de l'algorithme de Dikjstra, publié en 1959 par son inventeur, l'informaticien néerlandais Edsger Dijkstra : il sert en théorie des graphes à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Il s'applique à un graphe connexe dont le poids lié aux arêtes est positif ou nul. En théorie de la complexité, on démontre que cet algorithme est polynomial. |
Sélection(s) thématique(s) | Algorithmes classiques |
Mots-clés normalisés | algorithme classique ; algorithme de la théorie des graphes ; problème du plus court chemin ; algorithme de Dijkstra ; théorie de la complexité des algorithmes ; Dijkstra, Edsger : 1930-2002 |
Proposition autres mots-clés | |
Type documentaire | texte |
Typologie Générale | article |
Date de publication | 2010/11/16 |
Structure du document | atomique |
Niveau d'agrégation | 1.Le plus petit niveau (grain) |
Exigences techniques | |
Section Pédagogie | |
Type pédagogique | cours / présentation |
Public cible | enseignant |
Utilisation pédagogique | |
Section Relation | |
Type de la relation | est une partie de |
URL de la relation | http://www.irisa.fr/celtique/pichardie/teaching/L3/ALGO/ |
Section Droits | |
Droits du document | |
Section processus de validation (workflow) | |
Intervenants | Thierry ; Diane Rives (indexation); MG; DB |
Statut du workflow | publiée |
Signaler cette ressource. Si ce lien de signalement ne fonctionne pas (ouverture intempestive d'un mailer alors que vous utilisez un webmail) c'est qu'il vous manque l'extension idoine dans votre navigateur (par exemple l'extension send-mail pour firefox); c'est une bonne occasion de l'installer.