Algorithme de Warshall

L'algorithme de Warshall, parfois appelé algorithme de Roy-Warshall est un algorithme agissant sur un graphe. Il permet de construire la fermeture transitive d'un graphe orienté ou non orienté, c'est-à-dire de construire un deuxième graphe sur le même ensemble de sommet, avec un arc d'un sommet u à un sommet v, si et seulement si il existe un chemin dans le graphe original de u à v. Cet algorithme donne donc des informations sur les composantes connexes ou fortement connexes d'un graphe.

Texte : extrait de l'article Wikipédia « Algorithme de Warshall », sous licence CC BY-SA 4.0.