Exercices de programmation pour classes préparatoires
É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. On a dist.(i).(i) = 0 pour tout sommet i.
Rappel : l'algorithme de Floyd-Warshall considère successivement chaque sommet comme sommet intermédiaire possible des chemins.
Attention : quand dist.(i).(k) ou dist.(k).(j) vaut max_int, il ne faut pas additionner (risque de débordement arithmétique).
| Appel | Résultat attendu |
|---|---|
| floyd_warshall 3 [(0, 1, 4); (1, 2, 3); (0, 2, 10)] | [| [|0; 4; 7|]; [|max_int; 0; 3|]; [|max_int; max_int; 0|] |] |
| floyd_warshall 2 [(0, 1, 5); (1, 0, 2)] | [| [|0; 5|]; [|2; 0|] |] |
Connectez-vous pour soumettre du code.