Metraipolis › archive › dc_f27ee35bc7e1

Contractions hiérarchiques — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Contractions_hi%C3%A9rarchiques
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-05T13:58:22.132Z
SHA-256 of the archived text
8c550503fd6ad91bb4fbd363ea5a04a4b4d0829d57926b749b5bb77fa84e5aaf
Stable URL of this page
https://metraipolis.com/documento/dc_f27ee35bc7e1

How to cite

Contractions hiérarchiques — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Contractions_hi%C3%A9rarchiques (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f27ee35bc7e1 (Metraipolis archive dc_f27ee35bc7e1, sha256 8c550503fd6ad91bb4fbd363ea5a04a4b4d0829d57926b749b5bb77fa84e5aaf)
BibTeX
@misc{dcf27ee35bc7e1,
  title = {Contractions hiérarchiques — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Contractions_hi%C3%A9rarchiques},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f27ee35bc7e1; sha256 8c550503fd6ad91bb4fbd363ea5a04a4b4d0829d57926b749b5bb77fa84e5aaf},
  year = {2026}
}

Archived text

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

En mathématiques appliquées, la méthode des contractions hiérarchiques est une technique destinée à réduire le temps de calcul du plus court chemin grâce à la construction d'une représentation dite "contractée" du graphe initial sur laquelle sont exécutés des algorithmes adaptés aux recherches sur structure multi-niveaux. Les temps de calcul d’itinéraire issus de cette méthode peuvent être drastiquement plus rapides que l'algorithme de Dijkstra et surpasser de plus anciennes méthodes d'optimisation telles que les Highway Hierarchies. Elle a été proposée en 2008 par Robert Geisberger, Peter Sanders, Dominik Schultes, et Daniel Delling de l’université Karlsruhe Institute of Technology d’Allemagne. Comme Dijkstra, cette méthode peut permettre au sein d’un graphe routier, la récupération d’un plus court chemin comme la récupération de zones de chalandise. Cette méthode peut se scinder en au moins 2 phases : Une phase de prétraitement du graphe initial. Une phase d'exécution de la requête sur la représentation contractée du graphe. La première phase est vouée à générer plusieurs couches successives de représentation du graphe initial de plus en plus synthétiques. Aujourd'hui plusieurs outils open-source de calcul d'itinéraire utilisent cette méthode : OSRM, OpenTripPlanner, Graphhopper, Tempus, RoutingKit

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Contractions hiérarchiques» — https://fr.wikipedia.org/wiki/Contractions_hi%C3%A9rarchiques
Wikidata Q5165688: «in applied mathematics, a technique to speed up shortest-path routing» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5165688
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Contractions_hi%C3%A9rarchiques?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 230420131, consultata il 2026-11-05T13:55:33.688Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a6c73d42792954f5400adb5293e5c4efab2666462d832f491fc2352b797ba661