[PDF] Comparaison dalgorithmes de plus courts chemins sur des graphes

View - Download Comparaison dalgorithmes de plus courts chemins sur des graphes

Previous PDF

Next PDF

RAIRO. RECHERCHE OPÉRATIONNELLEC.PRINS

surdesgraphesroutiersdegrandetaille RAIRO. Recherche opérationnelle, tome 30, no4 (1996),p. 333-357

© AFCET, 1996, tous droits réservés.

L"accès aux archives de la revue " RAIRO. Recherche opérationnelle » implique l"accord avec les conditions générales d"utilisation (http://www. numdam.org/conditions). Toute utilisation commerciale ou impression systé- matique est constitutive d"une infraction pénale. Toute copie ou impression

de ce fichier doit contenir la présente mention de copyright.Article numérisé dans le cadre du programme

Numérisation de documents anciens mathématiques http://www.numdam.org/ Recherche opérationnelle/Opérations Research (vol 30
n 4 1996
pp

333-357

COMPARAISO

N

D'ALGORITHME

S D E PLU S COURT S

CHEMIN

S SU R DE S

GRAPHE

S

ROUTIER

S D E GRAND E TAILL E pa r C PRIN S l

Communiqu

pa r C

TAPIER

O

Résumé

Dans cet article, nous faisons le point sur les algorithmes de la littérature pour

lecalcul des plus courts chemins dans des grands graphes peu denses à valuations non négatives.Nous présentons ensuite les résultats d'une étude comparant des implémentations efficaces sur PC,appliquées à des graphes de grande taille modélisant des réseaux routiers. Sur des graphes à15000 sommets, certains algorithmes sont jusqu'à 218 fois plus rapides que l'algorithme classiquede Dijkstra.

Mot s clé s Plu s cour t chemin algorithme graph e pe u dense micro-ordinateur résea u routier

Abstract

In this paper we review the algorithms available for

Computing

shortest paths in

largesparse graphs with non-negative weights. We then present the results of a study comparing efficientPC-based implémentations, executed on large road-like networks. Some algorithms are up to 218times faster than Dijkstra's classical algorithm when run on graphs with 15000 nodes.

Keywords

Shortes

t path algorithm spars e graph microcomputer roa d network 1

INTRODUCTIO

N Ce t articl e résum e un e

étud

e [18 comparan t de s algorithme s efficace s pou r le s plu s court s chemin s dan s de s graphe s d e grand e taille pe u denses e t valuation s positives I l vis e troi s but s principau x a Fair e connaîtr e a u praticie n de s algorithme s efficace s permettan t d e dépasse r le s

éternel

s classique s de s livre s d e

Recherch

e

Opérationnell

e qu e son t le s algorithme s d e

Bellman

Dijkstra

Floy d e t Ford b

Montre

r qu e le s progrè s e n structure s d e donnée s e tquotesdbs_dbs20.pdfusesText_26

[PDF] algorithme problème du plus court chemin

[PDF] algorithme programmation c

[PDF] algorithme programmation calculatrice

[PDF] algorithme programmation cours pdf gratuit

[PDF] algorithme programmation pascal exercices pdf

[PDF] algorithme programmation python

[PDF] algorithme tri à bulle java

[PDF] algorithme tri à bulle langage c

[PDF] algorithme tri a bulle python

[PDF] algorithme tri par selection python

[PDF] algorithmic bias in recruitment

[PDF] algorithmique et programmation c

[PDF] algorithmique et programmation en java cours et exercices corrigés pdf

[PDF] algorithmique et programmation en pascal

[PDF] algorithmique et programmation en pascal (résumé)