Skip to Main content Skip to Navigation
Conference papers

Compromis espace-temps pour le problème de k plus courts chemins simples

Ali Al Zoobi 1 David Coudert 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Le problème de trouver k plus courts chemins simples (sans répétition de sommets) entre deux sommets dans un graphe a été largement étudié du point de vue de l'ingénierie algorithmique. Kurz et Mutzel (2016) ont proposé l'algorithme SB (pour Sidetrack Based) basé sur le concept de déviations, qui est actuellement la méthode la plus rapide en pratique. Dans ce travail, nous proposons deux améliorations de cet algorithme. Nous montrons tout d'abord comment accélérer l'algorithme SB en utilisant des mises à jour dynamiques d'arbres de plus courts chemins. Nos simulations réalisées sur certains réseaux routiers avec environ un demi-million de sommets et un million d'arcs montrent que notre amélioration donnent une accélération moyenne d'un facteur 1,5 à 2 avec une consommation de mémoire similaire à celle de l'algorithme SB. Notre principale contribution est un second algorithme réalisant un compromis entre temps d'exécution et mémoire utilisée. Notre algorithme permet de réduire significativement la mémoire de travail (d'un facteur 1, 5 à 2) au prix d'une légère augmentation du temps d'exécution.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-02835953
Contributor : David Coudert <>
Submitted on : Sunday, June 7, 2020 - 10:40:29 AM
Last modification on : Thursday, October 29, 2020 - 1:54:01 PM

File

algotel-FinalVersion.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02835953, version 1

Citation

Ali Al Zoobi, David Coudert, Nicolas Nisse. Compromis espace-temps pour le problème de k plus courts chemins simples. ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France. pp.4. ⟨hal-02835953⟩

Share

Metrics

Record views

71

Files downloads

169