Compromis espace-temps pour le problème de k plus courts chemins simples - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (1) , (1)
1

Abstract

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.
Fichier principal
Vignette du fichier
algotel-FinalVersion.pdf (322.35 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02835953 , version 1 (07-06-2020)

Identifiers

  • HAL Id : hal-02835953 , version 1

Cite

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⟩
113 View
110 Download

Share

Gmail Facebook Twitter LinkedIn More