Topological sort to find the number of paths to t

Question

I have to develop an O(|V|+|E|) algorithm related to topological sort which, in a directed acyclic graph (DAG), determines the number of paths from each vertex of the graph to t (t is a node with out-degree 0). I have developed a modification of DFS as follow:

DFS(G,t):
    for each vertex u ∈ V do
        color(u) = WHITE
        paths_to_t(u) = 0
    for each vertex u ∈ V do
        if color(u) == WHITE then
            DFS-Visit(u,t)

DFS-Visit(u,t):
    color(u) = GREY
    for each v ∈ neighbors(u) do
        if v == t then
            paths_to_t(u) = paths_to_t(u) + 1
        else then
            if color(v) == WHITE then
                DFS-Visit(v)
            paths_to_t(u) = paths_to_t(u) + paths_to_t(v)
    color(u) = BLACK

But I am not sure if this algorithm is related to topological sort or if should I restructure my work with another point of view.

Ayo

I assume your graph is a DAG (otherwise there is no point on talking about topological sort, nor about number of paths, there could be infinite number of those) – Munich

@Munich Yes, I put in the question "directed acyclic graph". I have edited to add the "DAG" abbreviation – Ayo

Your algo is correct, you do find the number of ways to t. And you do it in a topologically right manner: as soon as the vertex u is colored black, the value path_to_t(u) is correct -- it corresponds to pushing the vertex in the stack in topological sort algo. – Sparoid

Answer 1

It can be done using Dynamic Programming and topological sort as follows:

Topological sort the vertices, let the ordered vertices be v1,v2,...,vn
create new array of size t, let it be arr
init: arr[t] = 1
for i from t-1 to 1 (descending, inclusive):
    arr[i] = 0  
    for each edge (v_i,v_j) such that i < j <= t:
         arr[i] += arr[j]

When you are done, for each i in [1,t], arr[i] indicates the number of paths from vi to vt

Now, proving the above claim is easy (comparing to your algorithm, which I have no idea if its correct and how to prove it), it is done by induction:

Base: arr[t] == 1, and indeed there is a single path from t to t, the empty one.
Hypothesis: The claim is true for each k in range m < k <= t
Proof: We need to show the claim is correct for m.
Let's look at each out edge from vm: (v_m,v_i).
Thus, the number of paths to vt starting from v_m that use this edge (v_m,v_i). is exactly arr[i] (induction hypothesis). Summing all possibilities of out edges from v_m, gives us the total number of paths from v_m to v_t - and this is exactly what the algorithm do.
Thus, arr[m] = #paths from v_m to v_t

QED

Time complexity:
The first step (topological sort) takes O(V+E).
The loop iterate all edges once, and all vertices once, so it is O(V+E) as well.
This gives us total complexity of O(V+E)

Munich

I do not really know how it works dynamic programming. :( I forgot to indicate that the algorithm should be in O(|V|+|E|) – Ayo

@Ayo I added a correctness proof to the algorithm and a small optimization that makes sure time complexity is O(V+E). Dynamic programming is a technique that we build the solutions from the "easy" small case, up to the total solution for the problem, and this is what the loop after the topological sort does in the pseudo-code. – Munich

DP is redundant here. Why bother and enumerate the edges once again, if he already did the work in DFS? – Sparoid

@SergeyWeiss It is a suggested alternative to DFS, I believe this solution is very easy to prove, both its complexity and its correctness, and since the question seems theoretical - it is an important aspect. – Munich

@Munich Yes, DP approach is correct, it just seems an overkill here. And I have a small remark: you don't need additional checks on edges from vertex v_i. Since vertices are topologically sorted, v_j is already processed in previous iterations. Hence: for each edge (v_i,v_j) arr[i] += arr[j] – Sparoid

@SergeyWeiss Thank you both for your help! I will keep my solution if it's correct! :) But I will try to get how it works the solution based in DP too, just to learn a little bit about DP! :) – Ayo

@Ayo You are welcome! DP is a very powerful tool, it is certainly worthwhile to master this technique. There are a lot of sites where you can practice solving DP problems: topcoder, codeforces, SPOJ, etc. – Sparoid