Compromis espace-temps pour le problème de k plus courts chemins simples - IDEX UCA JEDI Université Côte d'Azur Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

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

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.
Fichier principal
Vignette du fichier
algotel-FinalVersion.pdf (322.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02835953 , version 1

Citer

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⟩
138 Consultations
132 Téléchargements

Partager

Gmail Facebook X LinkedIn More