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. On a dist[i][i] = 0 pour tout sommet i.
Rappel : l'algorithme de Floyd-Warshall considere successivement chaque sommet comme sommet intermediaire possible des chemins.
| Appel | Résultat attendu |
|---|---|
| floyd_warshall(3, [(0, 1, 4), (1, 2, 3), (0, 2, 10)]) | [[0, 4, 7], [inf, 0, 3], [inf, inf, 0]] |
| floyd_warshall(2, [(0, 1, 5), (1, 0, 2)]) | [[0, 5], [2, 0]] |
Connectez-vous pour soumettre du code.