Write the algorithm that finds and returns how many paths in k units of length between any given two nodes

QUESTION

Write the algorithm that finds and returns how many paths in k units of length between any given two nodes (source node, destination node; source and target nodes can also be the same) in a non-directional and unweighted line of N nodes represented as a neighborhood matrix. (Assume that each side in the unweighted diagram is one unit long.)

Note: By using the problem reduction method of the Transform and Conquer strategy, you have to make the given problem into another problem.

Algorithm howManyPath (M [0..N-1] [0..N-1], source, target, k)

// Input: NxN neighborhood matrix, source, destination nodes, k value.

// Output: In the given line, there are how many different paths of k units length between the given source and target node.

SUMMARY

A random matrix of size ‘N’ is taken. A source and a destination along ‘k’ are then taken as input. The number of possible paths from the source to the destination having size of ‘k’ units is then calculated by implementing a function called howManyPath().

EXPLANATION

The function called howManyPaths() is defined and used to calculate the number of paths of size ‘k’ units from the source to destination. The time complexity of this algorithm is said to be O(V^3). 

The naïve algorithm would give O(V^k) as the time complexity. The currently implemented algorithm below is the efficient algorithm having the time complexity as O(V^3).

ALGORITHM

Function howManyPath(M[0…N-1][0…N-1], source, target, k)

Allocate memory for count[N][N][k+1]

For every h from 0 to k

For every i from 0 to N-1

For every j from 0 to N-1

Assign 0 to count[i][j][e]

If (h=0) and (i=j), then

count[i][j][h]=1

If (h=1) and (M[i][j]=1), then

count[i][j][h]=1

if (h>1), then

for every a from 0 to N-1

if M[i][a]=1, then

count[i][j][h]=count[i][j][h]+count[a][j][h-1]

return count[u][v][k]

EXAMPLE

Take a matrix M :

0 1 1 1

0 0 0 1

0 0 0 1

0 0 0 0

And the values :

source = 0

target = 3 

k = 2

Then the possible paths are : 2

Also Read: Why are iterators useful?