Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is something that has been getting the best of me for past few days. Hopefully someone can point me get in the right direction.

I have a graph G, and I need to produce A which is the adjacent (adjacency) matrix in MatLab. In addition, I need to produce B which is another matrix that contains the length of the shortest path B(i,j) for i and j in graph G. Lets assume equal edge weights. The part I am having trouble with is producing B -- the shortest path. Why? Normally I would use nested loops to get this done (brute force method), however I would like for this to be done using matrix operations (one loop okay, just not nested).

Here is what I so far:

  1. I need to use an algorithm to find B (shortest path). I believe something like Dijkstra, Warshall or Floyd algorithm is the direction I need to go in. However they all apear to use some method of the "nested loops." Unless I am missing something.

  2. Transitive closure needs to be performed on on my adjacency matrix A however this requires one of above algorithms.

Any hints or directions would be much appreciated!

share|improve this question

1 Answer 1

up vote 0 down vote accepted

You could use the fact that $A^i(s,t)$ gives the number of different walks from $s$ to $t$ of exactly $i$ many steps. Thus, you could just compute $A^0, A^1, A^2, A^3, ...$ and keep the minimum exponent $i$ for which it is $A^i(s,t) > 0$, since such $i$ matches the distance. Here is an example that uses this fact:

% let B(s,t) keep the minimum power i with A^i(s,t) > 0
B=zeros(n,n);
for i=1:n
    B=B+(B<=0).*(A^i>0).*i;
end

% set main diagonal to zero (optional, otherwise get the 'return time')
B(eye(size(B))~=0)=0;

Some comments on the above code: for a connected graph, you can also break the loop after $diam(G)$ many steps, i.e., when B contains no zeros. Further, one could avoid computing $A^i$ in each step and use something like $Apow = Apow * A$ within the loop. Also note that here the main diagonal is manually set to zeros in the end, since starting the loop at $i=0$ does not work without further modifications (one would also have to flag unset entries within $B$ by another number than $0$ then, e.g., by $-1$).

However, note that this is just an example of how one could compute the shortest paths in Matlab with a single loop and matrix operations only. Its computational effort (including the above optimizations) is something like $\mathcal{O}(diam(G)*M(n))$ with $M(n)$ the effort of a matrix multiplication, thus, something like $\mathcal{O}(diam(G)*n^3)$. This is far from optimal, and especially bad for large sparse graphs. I do not believe that there is an efficient pure-matrix-operative solution to this problem. For example, the dynamic programming approach of Dijkstra, cannot efficiently be expressed in matrix form.

Unfortunately, Matlab again and again tells the user to avoid for-loops, since they are so 'slow'. But this tale does only hold for Matlab's horrible implementation of for-loops! In a real programming language, for-loops are much much faster than in Matlab, and they are even the most efficient way to access the memory in an arbitrary order that does not follow the access pattern of a matrix operation.

share|improve this answer
    
thanks for the information. The power of matrices is what I was looking for and your explanation and code has helped. Can you explain why you want to set the main diagonals to zero? They contain valid paths. –  Adam Oct 29 '12 at 21:56
    
It's just because, as for any distance measure, the shortest path distance from a node to itself is defined to be $0$, i.e., the length of the trivial/empty path. However, one can also keep these diagonal entries if they are of any use - they refer to the length of the shortest non-trivial path, which is always of length $>0$. –  cubic lettuce Oct 31 '12 at 7:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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