-1
$\begingroup$

Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk.

My question is that, say we have a DAG (directed acyclic graph), can DFS be a solution to the problem? I understand that native DFS would fail for the original problem as if there exists a cycle then we cannot traverse over the cycle to increase the path length from source to destination.

I've written the code tweaking DFS which I think solves the problem for a DAG.

I've used the inputs from a similar example, and have also compared the code both of which are based on the same algorithm.

//Pseudocode below:

public void printPossiblePaths(int u, int v, int k, int count, Queue queue) {
    Add vertex u to queue;
    Mark u as visited;

    foreach vertex w adjacent to u {
        If w is not visited {
            If count equals k before reaching 'v', ignore this vertex;

            if (count==k) {
                Print the path followed using the elements in the queue;
                Remove last element from the queue;
                return;
            }
            // Recur with the source as the new vertex and the updated queue
            printPossiblePaths(w, v, k, count, queue);
        }
    }
    Mark u as unvisited;
}

Gist of the algo:

1) Do a depth first search from the source vertex counting the edges as you go to.

2) Once you have traversed the k-edges, check if the node if we've arrived at the 'v'th node, otherwise come out of that path and check for other paths.

3) Similarly, if we do see the 'v'th node after 'k' edges, print the queue and check for for all other possible paths.

My question is : Is there a more efficient approach to achieve the same for a DAG or could we further tweak the code to handle cycles as well?

$\endgroup$
  • 1
    $\begingroup$ 1. What have you tried? Have you tried to prove your algorithm correct? Have you tried generating one million random small DAGs and seeing if your program works correctly on all of them (random testing)? You should try to answer your question on your own before asking here, and show us your attempts. 2. I don't think the question is answerable as it stands, as the question is awfully vague about what algorithm you have in mind. You'll need to say more about what solution you have in mind than just "DFS". Note that we don't read code here; we expect concise pseudocode. $\endgroup$ – D.W. Jul 15 '16 at 19:55
  • $\begingroup$ @Evil Thanks for pointing me to the link. Have updated the question accordingly :) $\endgroup$ – Shubham Mittal Jul 16 '16 at 19:37
0
$\begingroup$

I found the solution to this question. The idea is based on the following:

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

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

Thus the solution would be to build A and construct A^k using matrix multiplication (the usual trick for doing exponentiation applies here). Then just look up the necessary entry.

The final complexity would simply be $O(V^3 logk)$

$\endgroup$

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.