im writing a code to find the length of the shortest cycle in a graph. We need to use an n*n adjacency matrix for this and we evaluate A^k and the value for k at which the diagonal of A^k has at least one non-zero entry is the length of the shortest graph. I have a code for this but at this point, it spits out all values and not the smallest value of k only, my code;
thanks for any helpCode:
function sma(A)
[n,n] = size(A);
for k = 1:n;
P = A^k;
for k = 1:n;
if diag(A^k) == diag(zeros(n));
disp('no cycles for this graph exist');
else disp(min(k));
end
end
end
I ran the code and it seems to display all values of K, not the minimum. So the algorithm I'm trying to implement is like this;
for all values of k from 1 to n (size of square matrix),
compute A^k.
Now in the new set of matrices A^k, I need to find the smallest k such that A^k does not have a zero diagonal. So what I did for that was I compared the diagonal for each A^k with the diagonal of the zero matrix. If that was equal then that value of k is not valid. The code does that. The output when I ran the code is like 1, 2, 3, 4, 5 which is fine, but I only need it to display 1. If there are no such values of K, i.e. all powers of A^k have zero diagonals then it should display no graphs exist.
the code you gave me definitely gives me the minimum value but it also gives me an output like this;
K =
0 1 1 1
1 0 1 1
1 0 0 1
0 0 1 0
>> proj6(K)
the minimum cycle length of this graph is;
cycles for this graph do not exist
k =
2
the minimum cycle length of this graph is;
cycles for this graph do not exist
k =
2
the minimum cycle length of this graph is;
cycles for this graph do not exist
k =
2
the minimum cycle length of this graph is;
cycles for this graph do not exist
k =
2
i know the cycle doesn't exist for k=1, but it exists for k=2, so it should not be providing the output above. It also repeats itself four times