Exercices de programmation pour classes préparatoires
Ecrire une fonction floyd_warshall(n, aretes) qui calcule les plus courtes distances entre toutes les paires de sommets dans un graphe oriente pondere a poids positifs.
Entrees :
- n : le nombre de sommets (numerotes de 0 a n-1)
- aretes : une liste de triplets (u, v, poids) representant les aretes orientees
Sortie : une matrice (liste de listes) dist de taille n x n telle que dist[i][j] est la distance minimale de i a j, ou float('inf') s'il n'y a pas de chemin.
Rappel : Floyd-Warshall repose sur la programmation dynamique. On definit dist[i][j] et on met a jour pour chaque sommet intermediaire k : dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
| Appel | Résultat attendu |
|---|---|
| floyd_warshall(3, [(0, 1, 4), (1, 2, 3), (0, 2, 10)]) | [[0, 4, 7], ["float('inf')", 0, 3], ["float('inf')", "float('inf')", 0]] |
| floyd_warshall(2, [(0, 1, 5), (1, 0, 2)]) | [[0, 5], [2, 0]] |
Connectez-vous pour soumettre du code.