18

'Length' of a path is the number of edges in the path.

Given a source and a destination vertex, I want to find the number of paths form the source vertex to the destination vertex of given length k.

  • We can visit each vertex as many times as we want, so if a path from a to b goes like this: a -> c -> b -> c -> b it is considered valid. This means there can be cycles and we can go through the destination more than once.

  • Two vertices can be connected by more than one edge. So if vertex a an vertex b are connected by two edges, then the paths , a -> b via edge 1 and a -> b via edge 2 are considered different.

  • Number of vertices N is <= 70, and K, the length of the path, is <= 10^9.

  • As the answer can be very large, it is to be reported modulo some number.

Here is what I have thought so far:

We can use breadth-first-search without marking any vertices as visited, at each iteration, we keep track of the number of edges 'n_e' we required for that path and product 'p' of the number of duplicate edges each edge in our path has.

The search search should terminate if the n_e is greater than k, if we ever reach the destination with n_eequal to k, we terminate the search and add p to out count of number of paths.

I think it we could use a depth-first-search instead of breadth first search, as we do not need the shortest path and the size of Q used in breadth first search might not be enough.

The second algorithm i have am thinking about, is something similar to Floyd Warshall's Algorithm using this approach . Only we dont need a shortest path, so i am not sure this is correct.

The problem I have with my first algorithm is that 'K' can be upto 1000000000 and that means my search will run until it has 10^9 edges and n_e the edge count will be incremented by just 1 at each level, which will be very slow, and I am not sure it will ever terminate for large inputs.

So I need a different approach to solve this problem; any help would be greatly appreciated.

2
  • Do all of the edges have weight 1? Jan 11, 2013 at 5:45
  • @DennisMeng Yes, its an unweighted graph, i'll add it in the question
    – 2147483647
    Jan 11, 2013 at 5:48

3 Answers 3

43

So, here's a nifty graph theory trick that I remember for this one.

Make an adjacency matrix A. where A[i][j] is 1 if there is an edge between i and j, and 0 otherwise.

Then, the number of paths of length k between i and j is just the [i][j] entry of A^k.

So, to solve the problem, build A and construct A^k using matrix multiplication (the usual trick for doing exponentiation applies here). Then just look up the necessary entry.

EDIT: Well, you need to do the modular arithmetic inside the matrix multiplication to avoid overflow issues, but that's a much smaller detail.

9
  • "Then, the number of paths of length k between i and j is just the [i][j] entry of A^k." As every entry will be either 1 or 0, the number of paths will be either 0 or k?
    – 2147483647
    Jan 11, 2013 at 5:58
  • No. You can do a quick induction proof to show correctness if you'd like, but A^k will not have only 0s and ks. Jan 11, 2013 at 6:00
  • "A[i][j] is 1 if there is an edge between i and j, and 0 otherwise." you said that yourself
    – 2147483647
    Jan 11, 2013 at 6:01
  • Yes, but that does not imply that A^k has only 0s and ks. I'm doing exponentiation, not multiplication by a scalar. Jan 11, 2013 at 6:02
  • 3
    well, allocate more matrices via self-multiplication, say A0=A, A1=A0*A0, A2=A1*A1, etc, you'll end up only needing to multiply at most 2*ceil(log2(K)) times.
    – Vesper
    Jan 11, 2013 at 7:40
6

Actually the [i][j] entry of A^k shows the total different "walk", not "path", in each simple graph. We can easily prove it by "mathematical induction". However, the major question is to find total different "path" in a given graph. We there are a quite bit of different algorithm to solve, but the upper bound is as follow:

(n-2)*(n-3)*...(n-k) which "k" is the given parameter stating length of path.

1
  • This is indeed the correct word in graph theory, it should be noted. Finding paths is harder.
    – ZirconCode
    May 27, 2017 at 9:35
2

Let me add some more content to above answers (as this is the extended problem I faced). The extended problem is

Find the number of paths of length k in a given undirected tree.

The solution is simple for the given adjacency matrix A of the graph G find out Ak-1 and Ak and then count number of the 1s in the elements above the diagonal (or below).

Let me also add the python code.

import numpy as np

def count_paths(v, n, a):
    # v: number of vertices, n: expected path length
    paths = 0    
    b = np.array(a, copy=True)

    for i in range(n-2):
        b = np.dot(b, a)

    c = np.dot(b, a)
    x = c - b

    for i in range(v):
        for j in range(i+1, v):
            if x[i][j] == 1:
                paths = paths + 1

    return paths

print count_paths(5, 2, np.array([
                np.array([0, 1, 0, 0, 0]),
                np.array([1, 0, 1, 0, 1]),
                np.array([0, 1, 0, 1, 0]),
                np.array([0, 0, 1, 0, 0]),
                np.array([0, 1, 0, 0, 0])
            ])

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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