Après avoir implémenté l'algorithme de Floyd dans notre projet, nous nous sommes rendus compte que celui-ci a un coût calcul très élevé dès que le nombre de cellules (nbCell) est grand. D'après nos calculs, la complexité de l'algorithme est de O(nbCell^6). Par conséquent, avec une carte de dimension nbCell = 35, l'algorithme met plus de 36 secondes à s'exécuter (il passe 35^6 = 1'838'265'625 fois dans la boucle) sur le terminal EPFL, alors que ce calcul semble presque instantané (moins de 1 seconde) sur la démo.
Devons nous atteindre de telles performances ? Si oui, comment optimiser l'exécution de l'algorithme ?
Il est facile de diviser le temps d'exécution par 2 en utilisant le fait que le chemin de A à B est de même longueur que le chemin de B à A et donc éviter de calculer les résultats deux fois. Cependant, cela nous ramène à 18 secondes, ce qui reste très grand...