La robustesse est une caractéristique essentielle à tous réseaux de transport, elle garantie la qualité du service même en cas de perturbation.

L'une des approches permettant de quantifier cette robustesse est basée sur le nombre de chemins alternatifs. Cependant, les algorithmes de la littérature réalisant cette tâche sont de complexité quartique.

Dans ce papier, nous proposons une nouvelle approche permettant de calculer des chemins alternatifs basée sur l'algorithme de Floyd dont la complexité est cubique.