Number of paths - acyclic graphs

This is a quick post (I should be working now). Yesterday, I heard a college of mine asking: "how many paths are between these two cities?". The guy next to me looked for an answer in Google (as we always do), and found a very interesting forum that solved his problem.

http://boards.straightdope.com/sdmb/showthread.php?t=396094

I personally read it, and I didn't like what I saw. I mean, if you have a problem like this one, please, read something about graph theory.

If you have an acyclic graph things are much simpler, I'll explain how to do this with an example:

Let's say you have the following graph (It also works with undirected graphs):

The length of the longest (possible) path in an acyclic graph is equal to the number of vertices minus 1 (in this case 3) . The adjacency matrix gives us a lot of information. If you multiple this matrix twice, you get:

This new matrix shows the number of paths of length 2 between two vertices, for example, the number of paths of length 2 between v1 and v3 is 1. So if you want to get the number of possible paths you only need to do:

It's not my intention to say that this is the best solution, but I would like to point out that there are other possibilities than algorithms taken from a forum :-).

Then we can talk about graphs with cycles, but I should get back to work!

Cheers!