Développement : Algorithme de Floyd-Warshall

Détails/Enoncé :

Soit $G = (S,A)$ et $w : A \to \mathbb{R}$ une fonction de poids. On peut trouver toutes les plus courtes distances entre les paires de sommet si $G$ n'a pas de cycle de poids négatif ou trouver un cycle de poids négatif en $O( |S|^3)$.

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :

Références utilisées dans les versions de ce développement :

Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)
Types de données et algorithmes, Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria (utilisée dans 9 versions au total)