Metraipolis › archive › dc_ec728f007e91

Algorithme de Dijkstra — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T15:40:00.429Z
SHA-256 of the archived text
c9e8d487a5851ed7e83e0e11fc3936f5a447240d60ce20d933e7f8708cc9e71f
Stable URL of this page
https://metraipolis.com/documento/dc_ec728f007e91

How to cite

Algorithme de Dijkstra — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ec728f007e91 (Metraipolis archive dc_ec728f007e91, sha256 c9e8d487a5851ed7e83e0e11fc3936f5a447240d60ce20d933e7f8708cc9e71f)
BibTeX
@misc{dcec728f007e91,
  title = {Algorithme de Dijkstra — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ec728f007e91; sha256 c9e8d487a5851ed7e83e0e11fc3936f5a447240d60ce20d933e7f8708cc9e71f},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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, dans un graphe orienté pondéré par des réels positifs G = ( S , A ) {\displaystyle G=(S,A)} , il calcule des plus courts chemins à partir d'une source vers tous les autres sommets. 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. La complexité temporelle de l'algorithme de Dijkstra dépend de la structure de données utilisée pour la file de priorité : Avec une file de priorité implémentée par un tas binaire : la complexité est en O ( X X ( | A | + | S | ) log ( | S | ) ) {\displaystyle {\mathcal {O}}\left({\vphantom {X^{X}}}(|A|+|S|)\log(|S|)\right)} , où | A | {\displaystyle |A|} est le nombre d'arêtes et | S | {\displaystyle |S|} le nombre de sommets du graphe. Avec une file de priorité implémentée par un tas de Fibonacci : la complexité est améliorée à O ( X X | A | + | S | log ( | S | ) ) {\displaystyle {\mathcal {O}}\left({\vphantom {X^{X}}}|A|+|S|\log(|S|)\right)} . Ces complexités s'appliquent aux graphes avec des poids d'arêtes positifs. Pour les graphes comportant des arêtes de poids négatif, l'algorithme de Bellman-Ford est généralement préféré.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»).
Fonte: Wikipedia in francese, voce «Algorithme de Dijkstra» — https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Wikidata Q8548 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q8548
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 238879476, consultata il 2026-10-15T15:08:00.199Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b8c8dc95ac23aac3d8ec545d404664ca9683582a3f1d17ed901fff7f5283b03e