| Property |
Value |
| dbo:abstract
|
- En théorie des graphes, l'algorithme de Dijkstra (prononcé [dɛɪkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée. L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra, et a été publié en 1959. Cet algorithme est de complexité polynomiale. Plus précisément, pour sommets et arcs, le temps est en , voire en . (fr)
- En théorie des graphes, l'algorithme de Dijkstra (prononcé [dɛɪkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée. L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra, et a été publié en 1959. Cet algorithme est de complexité polynomiale. Plus précisément, pour sommets et arcs, le temps est en , voire en . (fr)
|
| dbo:basedOn
| |
| dbo:discoverer
| |
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 21563 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:float
| |
| prop-fr:image
|
- DijkstraBis01.svg (fr)
- DijkstraBis02.svg (fr)
- DijkstraBis03.svg (fr)
- DijkstraBis04.svg (fr)
- DijkstraBis05.svg (fr)
- DijkstraBis06.svg (fr)
- DijkstraBis07.svg (fr)
- DijkstraBis08.svg (fr)
- DijkstraBis09.svg (fr)
- DijkstraBis01.svg (fr)
- DijkstraBis02.svg (fr)
- DijkstraBis03.svg (fr)
- DijkstraBis04.svg (fr)
- DijkstraBis05.svg (fr)
- DijkstraBis06.svg (fr)
- DijkstraBis07.svg (fr)
- DijkstraBis08.svg (fr)
- DijkstraBis09.svg (fr)
|
| prop-fr:légende
|
- Étape 4 : on choisit E. On met à jour le voisin J . (fr)
- Étape 9 : la ville dont la distance est la plus courte est J . On choisit J et on l'ajoute au sous-graphe. On s'arrête puisque la ville d'arrivée est maintenant dans le sous-graphe. (fr)
- Étape 8 : la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I . (fr)
- Étape 5 : la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G et la ville H . (fr)
- Étape 3 : on choisit F. On met à jour le voisin I . (fr)
- Étape 2 : on choisit la ville B. En effet, c'est la ville hors du sous-graphe qui est à la distance minimale . On met à jour le seul voisin . Sa distance devient 85+80 = 165. (fr)
- Étape 7 : la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance. (fr)
- Étape 1 : on choisit la ville A. On met à jour les villes voisines de A qui sont B, C, et E. Leurs distances deviennent respectivement 85, 217, 173, tandis que les autres villes restent à une distance infinie. (fr)
- Étape 6 : la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville H . On choisit donc H. On met à jour la ville D et la ville J . (fr)
- Étape 4 : on choisit E. On met à jour le voisin J . (fr)
- Étape 9 : la ville dont la distance est la plus courte est J . On choisit J et on l'ajoute au sous-graphe. On s'arrête puisque la ville d'arrivée est maintenant dans le sous-graphe. (fr)
- Étape 8 : la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I . (fr)
- Étape 5 : la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G et la ville H . (fr)
- Étape 3 : on choisit F. On met à jour le voisin I . (fr)
- Étape 2 : on choisit la ville B. En effet, c'est la ville hors du sous-graphe qui est à la distance minimale . On met à jour le seul voisin . Sa distance devient 85+80 = 165. (fr)
- Étape 7 : la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance. (fr)
- Étape 1 : on choisit la ville A. On met à jour les villes voisines de A qui sont B, C, et E. Leurs distances deviennent respectivement 85, 217, 173, tandis que les autres villes restent à une distance infinie. (fr)
- Étape 6 : la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville H . On choisit donc H. On met à jour la ville D et la ville J . (fr)
|
| prop-fr:titre
|
- Animation d'un algorithme de Dijkstra (fr)
- Animation d'un algorithme de Dijkstra (fr)
|
| prop-fr:upright
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie des graphes, l'algorithme de Dijkstra (prononcé [dɛɪkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée. (fr)
- En théorie des graphes, l'algorithme de Dijkstra (prononcé [dɛɪkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée. (fr)
|
| rdfs:label
|
- Algorithme de Dijkstra (fr)
- Dijkstra's algorithm (en)
- Dijkstraren algoritmo (eu)
- Thuật toán Dijkstra (vi)
- Алгоритм Дейкстри (uk)
- Алгоритм Дейкстры (ru)
- ダイクストラ法 (ja)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:basedOn
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is prop-fr:œuvresPrincipales
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
