Prépa Code Connexion Inscription

Écrire une fonction floyd_warshall : int -> (int * int * int) list -> int array array qui calcule les plus courtes distances entre toutes les paires de sommets dans un graphe orienté pondéré à poids positifs.

Entrées : - n : le nombre de sommets (numérotés de 0 à n-1) - aretes : une liste de triplets (u, v, poids) représentant les arêtes orientées

Sortie : une matrice (tableau de tableaux) dist de taille n × n telle que dist.(i).(j) est la distance minimale de i à j, ou max_int s'il n'y a pas de chemin.

Rappel : Floyd-Warshall repose sur la programmation dynamique. On met à jour pour chaque sommet intermédiaire k : dist.(i).(j) <- min dist.(i).(j) (dist.(i).(k) + dist.(k).(j)).

Attention : quand dist.(i).(k) ou dist.(k).(j) vaut max_int, il ne faut pas additionner (risque de débordement arithmétique).