Why does this solution say the DFS have to run in reverse?

2
votes

Wouldn't it keep finding t if we start at s?

Give a linear-time algorithm that takes as input a directed acyclic graph G = (V,E) and two vertices s and t, and returns the number of paths from s to t in G.

solution:

The basic idea here is to start at vertex t, and use depth-first search in reverse direction until we reach vertex s. Each and maintains a counter which indicates the number of unique reverse paths found from vertex t.

  1. Initialize counters to 0 for all vertices.
  2. Start depth-first-search in reverse direction using vertex t as a root.
  3. For each edge (u, y) examined in the breadth-first search. Counter(v) = max{ Counter(v) + 1, Counter(v) + Counter(u) }
  4. Return Counter(s).
2
algorithmdepth-first-search
The question explicitly says start at t, not s. And the point is t see how may unique reverse paths there are from t to s. – John Weldon
The quoted text first talks about DFS and then about BFS, so which is it? I don't think DFS would work in any direction, because you would always end up with Counter(s) being 1 (or 0). – svick
And I don't see how would this work with BFS either. – svick
john Weldon: I separated the question and the solution i found to make it more clear. – jfisk

2 Answers

0
votes

You can try this: (this is from http://arxiv.org/PS_cache/cond-mat/pdf/0308/0308217v1.pdf, Pg 5).

We will give weights to different vertices starting with s, based on the number of paths to the vertex from S and also set their distance based on the no of edges they are away from s.

  1. Start with wt(S) = 1 and d(s) = 0;
  2. Every vertex i adjacent to S is given weight = w(s) = 1 and d(i) = (d) +1;

  3. For each vertex j adjacent to one of these vertices and d(j) not yet defined, if w(j) = 0, then assigned w(i)=w(j) /that is assign the wt of parent to j/ else if d(j)=d(i) +1 , then w(j) = w(i) + 1.

  4. Repeat step 3 till T is reached. The wt(t) will give the number of shortest paths from s to T.

Accordingly, the paper explains why this is linear.

0
votes

There is no need to run the algorithm in reverse. You can count the solutions in linear time also with a forward search. I don't think the solution says that you need to do it in reverse, and you don't.

Both forward and reverse search are based on the same general identity, which is that

number-of-paths(s, t) =
  sum over nodes 'c' of any cut of the graph that separates s from t:
    number-of-paths(s, c) * number-of-paths(c, t)