Optimisation de l´utilisation de l´algorithme de Dijkstra pour un simulateur multi-agents spatialisé

Les techniques de mod?lisation bas?es sur le d?pla-cement d´agents dans une topologie de type graphe s´av?rent une approche fructueuse. Beaucoup de mod?les li?s aux d?placements d´agents utilisent l´algorithme de Dijkstra pour construire, ? coup s?r, les plus courts chemins. Cependant un probl?me majeur de ces mod?les est la fr?quence ? laquelle les nombreux agents, durant toute la simulation, utilisent Dijkstra pour construire leurs plus courts chemins entre les positions o? ils se trou-vent et les positions o? ils veulent se rendre. Cette utilisation massive de l´algorithme n?cessite un grand temps de calcul. Dans cet article, nous proposons un algorithme permettant une optimisation spatiale de la repr?sentation informatique d´un graphe (matrice d´adjacence, liste d´adjacence), suivi d´un stockage optimis? de tout plus court chemin une fois construit. Cette optimisation ?vite aux agents d´avoir ? reconstruire des chemins d?j? construits et supprim?s. Ce qui r?duit consid?rablement le temps de calcul d? ? la construction de plus court chemins.