Getting B+ matrix (Warshall algorithm) in Matlab

Question

Pseudocode:

// B = nxn binary matrix
// Bm = resulting matrix
for (i=1; i<=n; i++)
{
 for (j=1; j<=n; j++)
 {
 if (B[i,j] == 1)
 {
 for (k=1; k<=n; k++)
 {
 Bm[i,j] = B[i,j] | B[k,j];
 }
 }
 }
}

This is the Warshall algorithm written (in my way):

B = [1 1 0 0 0; 0 0 0 1 0; 0 0 0 0 1; 0 1 0 0 0; 0 0 0 0 0];
n = 5;
Bm = zeros(n);
for i = 1:n
 for j = 1:n
 if B(i,j) == 1
 for k = 1:n
 Bm(i,k) = B(i,k) | B(k,j);
 end
 end
 end
end

It works but, how can I improve the matrix loops?

• Quentin Pradet: Did you mean Bm(i,j) = B(i,k) | B(k,j)?

Answer 1

This post may help you in removing a loop: http://mathforum.org/kb/message.jspa?messageID=845980

Furthermore, one way to speed up your code is to use a short circuit logical operator:

B(i,k) || B(k,j); 

Also it seems to have a small effect if you use a logical matrix as input rather than a double:

B = logical(b);

Last and least, it would be nicer to initialize Bm with the datatype that it will have:

Bm = false(n)