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.
Best Answer
Try asking on http://ask.sagemath.org/questions/
In fact, there was already a general question asked there about Sage versus other software, and the top answer said, "If you are doing graph theory or serious number theory, you shouldn't even be asking the question of which package to use." That is, if you're doing graph theory, or serious number theory, Sage is the winner by far. This was comparing Sage to all other computer algebra systems. So, I believe the answer is Sage is the best graph theory program that exists. And, it is getting better all the time.
http://ask.sagemath.org/question/1010/reliability-of-sage-vs-commercial-software
Sage combines together many open source graph theory tools that exist (nauty generator, networkx which contains tons of stuff by itself, cliquer, and more) and also all the things that have been programmed by Sage developers. And, if there is anything you want to be able to do that isn't already programmed, you can program it in Python (or if you need it to be really fast, in cython).
As far as visualization, yes, Sage graphs are extremely good graphics. If you save them to a PDF, you can zoom in as much as you want (I'm not exaggerating) and they will still be crisp, clean graphics. And, there is a graph editor that allows you to draw graphs and move the vertices around and add vertices and edges and things like that. Not to mention, there are many built in graphs.
Oh, and by the way, if Mathematica (or one of many other programs) is installed on the same computer as Sage, you can use the functions from those other programs and get the results in Sage.
Here's a video tutorial on graph theory (second video from top). It gives a lot of detail, and includes all the info on graphics such as saving pdfs and using the graph editor to make nice looking graphs.
http://www.sagemath.org/help-video.html
Here's a real quick tutorial on graph theory in Sage:
http://steinertriples.fr/ncohen/tut/Graphs/
Here are the functions available:
And here are some graphs you can easily generate: