Algorithme de Floyd- Warshall en CamL

Fermé
Lachauve67 - 30 oct. 2014 à 16:10
Bonjour !
J'aimerais un petit coup de pouce pour programmer l'algorithme de Floyd Warshall en CamL.
L'algorithme de Floyd Warshall donne la matrice des plus courts chemins si on entre la matrice d'adjacence d'un graphe pondéré.

Les chemins impossibles sont représentés par l'infini dans la matrice, j'ai donc tout d'abord implémenté le type "entier" qui correspond à la réunion de N et +infini.

De plus, on sait que
(a i,j)^(k+1) = min ( (a i,j)^k , (a i,k+1)^k + (a k+1,j)^k ), c'est de cette manière qu'on définit la matrice suivante.

J'ai donc écrit le code suivant : (le 2ieme et 3ieme programme permettent de prolonger la fonction min et l'addition sur le type entier)
____________
type entier = infini | N of int;;
____________
let mini a b = match a,b with
infini,infini -> infini
|infini, N(b) -> N(b)
|N(b),infini -> N(b)
|N(a),N(b) -> N(min a b);;
____________
let plus a b = match a,b with
infini, infini -> infini
|infini, N(a) -> infini
|N(a) ,infini -> infini
|N(a), N(b) -> N(a+b);;
____________
let puissance_fw graph =
let n = vect_length graph in
let a = make_matrix n n infini in
for i = 0 to (n-1) do
for j = 0 to (n-1) do
a.(i).(j) <- N(graph.(i).(j))
done;
done;
for k = 0 to (n-1) do
for i = 0 to (n-1) do
for j = 0 to (n-1) do
a.(i).(j) <- mini ((a.(i).(j))) (N((a.(i).(k) + a(k).(j) )))
(** Il y a un problème de type dans cette ligne**)
done;
done;
done;
a;;
____________
____________

J'ai donc comme vous avez pu le lire, un problème de type dans la ligne citée plus haut que je n'arrive pas résoudre. Pourriez-vous m'expliquer d'où celui-ci provient et comment le résoudre ?
Je vous remercie d'avance.
Bonne soirée à vous!