Is there a formula to figure out how many different paths in a given graph considering we know what the initial and terminal vertex and length of the path?

I was figuring out how many different paths for a k subscript 4 graph (complete graph) and found 5 different path. But it turns out it actually has 7 different paths from the answers in tbe path. It seems I am always off by little when the length is small but my answer is off by a lot when the question gives me a larger length of the path.

Sounds like homework? We're not allowed to help directly with homework, and I can't help much without totally giving it away.

The main question is: Are you counting paths that include cycles, or not?

Sounds like homework? We're not allowed to help directly with homework, and I can't help much without totally giving it away.The main question is: Are you counting paths that include cycles, or not?

The formula in the book uses adjacency matrix and change the values given the row and column entries. But it is presented with no context beyond after introducing the adjacency matrix. And yes, cycles are allowed.

Does the hint involve the adjacency matrix? The book example does a poor job making use of it to find the number of different paths in the graph...

A hint or two is sufficient.

The cells in the adjacency matrix represent the possible edges of the graph. Putting values in the cells is the same as assigning a value to that edge.

Hint: Think of an algorithm that can read/write whatever values it needs on the edges in order to count paths through the graph.

You can use recursive function to fire all paths and store sufficient ones (length, node containing). But there is not any mathematic formula for the count, since formula cannot depend on specified particular node pair as such.

If the adjacency matrix is M and the length is l, M^l times a column vector that has a 1 in the position of the start node and 0s elsewhere will be a column vector that tells you how many paths of length l there are from that start node to any other node. Pick the coordinate corresponding to your target node, and you'll be done.

If the adjacency matrix is M and the length is l, M^l times a column vector that has a 1 in the position of the start node and 0s elsewhere will be a column vector that tells you how many paths of length l there are from that start node to any other node. Pick the coordinate corresponding to your target node, and you'll be done.

Well I taught myself matrix multiplication and figured some of the things you are saying. I produced a M ^ 3 where M is the matrix and 3 is the length given in the problem. The column vector produced a 7 where the 1 used to be in the original matrix and 6 where the 0 used to be in the original graph.

Maybe you can post the graph, the start and end node, the matrix and the computations you did, so we have some idea of what you are saying.

EDIT: Oh, K4, as in the complete graph with 4 vertices.

(0 1 1 1)^3 (1)   (6)
(1 0 1 1)   (0) = (7)
(1 1 0 1)   (0)   (7)
(1 1 1 0)   (0)   (7)

That is correct.

Maybe you can post the graph, the start and end node, the matrix and the computations you did, so we have some idea of what you are saying.EDIT: Oh, K4, as in the complete graph with 4 vertices.

(0 1 1 1)^3 (1)   (6)(1 0 1 1)   (0) = (7)(1 1 0 1)   (0)   (7)(1 1 1 0)   (0)   (7)

That is correct.

Yes k subscript 4 (complete graph) just as stated in the original post.

I guessed the question now to confirm my understanding is why and how is 7 the answer and not 6 right off the bat by inspecting the column vector? Is it because we pick the higher number in the column vector (4 × 1 matrix)?

I'll try to explain this in a less abstract manner (still using K4).

Your starting matrix starts out:

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

In this example, what each cell is saying at this point is "how many ways can I get from vertex X to vertex Y in one step?"

Multiply it by itself once, and you get:

3 2 2 2
2 3 2 2
2 2 3 2
2 2 2 3

At this point you have "how many ways can I get from vertex X to vertex Y in 2 steps?"

Notice that the diagonal cells have 3, and everything else has 2.

Let's double check to make sure the cells contain what makes sense...

The diagonals represent the number of ways you can go from a vertex back to itself in two steps. Since all edges are bidirectional, you can just follow an edge and then come back on the same edge. Since K4's vertices all have 3 edges, there are 3 paths.

The cells with 2 in them are because you must use 2 edges - if your first move was to go to the goal vertex, your second move would require you to leave the goal, invalidating that path. Since there are only two alternatives, there are only two paths.

So, everything checks out so far.


If you multiply a third time, you get:

6 7 7 7
7 6 7 7
7 7 6 7
7 7 7 6

Note: For this particular problem, you don't even need to multiply by a column vector like Alvaro suggests; you can just extract the desired [from,to] cell right out of the matrix itself, since that's what's going to happen any time you multiply by a column vector that has a 1 and the rest 0 (this extracts the column that the 1 corresponds to). Multiplying by a column vector IS necessary when you're trying to solve a more complex problem (such as a probability problem with a stochastic matrix).


So, the real question is: Why does the matrix multiply operation work on this problem? Let's take a look at what one step of matrix multiplication is doing. Let's go back to the 2-length path, multiplying the matrix by itself once, and look at two of the result cells.

For the upper left cell, the involved cells during multiplication are:

0 1 1 1     0 . . .     3 . . .     
. . . .  *  1 . . .  =  . . . .
. . . .     1 . . .     . . . .
. . . .     1 . . .     . . . .

The first step of multiplying is 0*0. This is essentially saying "There aren't any ways to go from vertex 0 to vertex 0, and then to vertex 0".
The second step is 1*1. This is saying "There's one path from vertex 0 to vertex 1, and one path from vertex 1 back to vertex 0, so combine them by multiplying them together and there's one total path."
(The last two steps are the same as step 2)
Then each of the four partial results are added together and put in the result cell.


For the non-diagonal cells:

0 1 1 1     . 1 . .     . 2 . .
. . . .  *  . 0 . .  =  . . . .
. . . .     . 1 . .     . . . .
. . . .     . 1 . .     . . . .

0 paths from V0 -> V0 in one step * 1 path from V0 -> V1 in one step = 0 paths.
1 path from V0 -> V1 in one step * 0 paths from V1 -> V1 in one step = 0 paths.
1 path from V0 -> V2 in one step * 1 path from V2 -> V1 in one step = 1 path.
1 path from V0 -> V3 in one step * 1 path from V3 -> V1 in one step = 1 path.
Total: 2 paths starting at V0 and ending at V1 taking 2 steps.


For the second multiply (paths of length 3), let's do the same thing.

Using our M^2 matrix and multiplying it again by M, let's examine the first two result cells again.

3 2 2 2     0 . . .     6 . . .     
. . . .  *  1 . . .  =  . . . .
. . . .     1 . . .     . . . .
. . . .     1 . . .     . . . .

There are 3 ways to move from V0 -> V0 in two steps, but no way to go from V0 -> V0 in one step, so no valid paths using this combination of steps.
There are 2 ways to move from V0 -> V1 in two steps, and one way to go from V1 -> V0 in one step, so two total paths.
(same for the remaining two options)
Total: 6 paths.

3 2 2 2     . 1 . .     . 7 . .     
. . . .  *  . 0 . .  =  . . . .
. . . .     . 1 . .     . . . .
. . . .     . 1 . .     . . . .

3 paths from V0 -> V0 in 2 steps * 1 path from V0 -> V1 in 1 step = 3 paths.
2 paths from V0 -> V1 in 2 steps * 0 paths from V1 -> V1 in 1 step = 0 paths.
2 paths from V0 -> V2 in 2 steps * 1 path from V2 -> V1 in 1 step = 2 paths.
2 paths from V0 -> V3 in 2 steps * 1 path from V3 -> V1 in 1 step = 2 paths.
Total: 7 paths.


This method works:
- On digraphs.
- On graphs with multiple edges connecting the same pair of vertices.
- On graphs with loops.

It does NOT work:
- If you need to exclude cycles.


I haven't tried proving it, but you might be able to modify the algorithm to discard cycles if you zero out the diagonal manually before each single-step matrix multiply. Maybe. I'll have to try it sometime and see if that actually works.