# relax.oct (brg 3-Feb-2003)
# This is an Octave program which takes as input a matrix M and repeatedly
# performs the relaxation M_ij = min(M_ij, M_ik + M_kj) on it. This is
# a useful function for certain network routing algorithms.

function B = relax (A)
    n = rows(A);
	B = A;
	for i = 1:n
		for j = 1:n
			for k = 1:n
				B(i,j) = min(B(i,j), A(i,k) + A(k,j));
			endfor
		endfor
	endfor
endfunction

while true
	OUT = relax(IN)
	if (OUT == IN)
		break
	else
		IN = OUT;
	endif
endwhile