CODEWITHSUNDEEP
algorithmgraphpathgraph-theory
geek2geek_AWS
geek2geek_AWS

Reputation: 566

Graph Algorithm to count all possible paths between different starting vertices and one end vertex

I am trying to find the time efficient algorithm for the following task

Given a set of pages A, B, C, D, E where A,B,C,D can be starting points but E will always be a ending point. The following representing connections between pages (A,B), (A,B), (A,C), (A,E), (B,A), (B,C), (C,A), (C,E), (C,D), (D,E), (D,A). Now if I choose A as starting point and E as ending point then I have to find all possible paths between A and E whose path length is at most 4 in a time efficient manner. So all possible paths between A and E with at most path length 4 are

A->E

A->D->E

A->C->D->E

A->B->C->E

A->B->C->E

A->B->A->E and many more

Note 1: Two edges between two same vertices are treated as different and also order of vertices also important. A cycle can exist in Graph.

Note 2: Only way to break the infinite loop search is by constraint of maximum limit of path length.

Upvotes: 0

Views: 3846

Answers (2)

Pham Trung
Pham Trung

Reputation: 11284

This problem can be solved by dynamic programming.

We can represent each step by two parameter, the current node and the number of step which are already taken (node, step)

Pseudo code:

int[][]dp;
int getNumberOfWay(int node, int step){
   if(step == 4)
      if(node == end node)
         return 1;
      return 0; 

   if(already visit this step)
      return dp[node][step];
   int result = 0;
   if(node == end node)
      result++; 
   for(node that has edges coming from this node)
      result += getNumberOfWay(next node, step + 1);
   return dp[node][step] = result;
}

Time complexity for this is O(4*E*N) with E is number of edge and N is number of node.

Note: the problem can also be improved if we traverse the graph from the end node, rather than 4 start nodes.

Upvotes: 2

nevets
nevets

Reputation: 4818

It can be solved using matrix multiplication.

Let's say A[i][j] denotes the total way to walk from i to j, then we have A'[i][j] = A[i][k] * A[k][j] because of multiplication rule of combination. And we can see that this formula is in a form of matrix multiplication.

Therefore, we can construct a matrix A with N rows and columns, where N is the totals number of pages. Then A[i][j] denotes the initial ways to go to j starting from i. For example, initial A for your problem will be:

  A B C D E
A 0 2 1 0 1
B 1 0 1 0 0
C 1 0 0 1 1
D 1 0 0 0 1
E 0 0 0 0 0

Next, we just need to calculate A[0..3][4] + A^2[0..3][4] + A^3[0..3][4] + A^4[0..3][4], where A^k means the A to the power of k.

The good thing about using matrix multiplication is it could be extended to a more general question: how many paths from i to j could be formed using exactly K steps?.

In this case, we only need to calculate A^k, which could be sped up using exponentiation by squaring and solved in O(log k) * O(N^3), where O(N^3) is the complexity of matrix multiplication.

Upvotes: 1

Related Questions