Given a directed graph, we need to find the number of paths with exactly k edges from source u to the destination v.
We use adjacency matrix
of the given graph in which value of adj[i][j]
represents if there is an edge from vertex i
to vertex j
in the graph. If the value is 1
then there is an edge from vertex i
to vertex j
else, if value is 0
then there is no edges from vertex i
to vertex j
in the graph.
To understand the problem let's take an example of a graph with 6 vertices {0, 1, 2, 3, 4, 5} and edges. Now let's find number of paths from vertex 0
to vertex 2
with 2 edges. Below a diagram of the graph is given:
This is a companion discussion topic for the original entry at http://iq.opengenus.org/number-of-paths-with-k-edges/