3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Did you mean Bm(i,j) = B(i,k) | B(k,j)? \$\endgroup\$ – Quentin Pradet May 7 '13 at 13:48
2
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.