Possible paths between points in network

Question

In my Operations Management course, we are given a set of nodes in a graph $\{A,B,C,D,E,F,G,H,I\}$, and are given a set of predecessor nodes, i.e., nodes that immediately come before the given node in the graph as $\{NULL, A, A, B, C, (D,E), (D,E), F, G\}$. I.e., nothing immediately precedes A, but A immediately comes before B, and D and E come immediately before F.

My question is: Without drawing a graph, is it possible to figure out the paths that connect node $A$ to node $I$? We are told that there are 4 such paths.

Thanks!

Answer 1

My strategy was working backwards. I must be preceded by G, G can be preceded by either D or E, so you need two possible cases. At this point my tableau looks like $$\frac{D}{E}GI$$ Then D can only be preceeded by B which can only be preceeded by A, and E can only be preceeded by C which can only be preceeded by A. Since we got to the root in all of our cases, we are done. The tableau looks like$$\frac{ABD}{ACE}GI$$

So we read off from that that the two possible paths are ABDGI and ACEGI,

Answer 2

You may try depth frist search

$$\begin{align}-~~&A& A~~& B& C&~~~ (D,E)& (D,E)~~& F& G \\ A~~~ & B & C~~ & D~~ & E~~~ & F~ & G~~&H~~&I \end{align}$$

> From A  two edges, to B and C  (C, B)   
    From B  one edge, to D (C, D)
      From D two edges, to F and G (C, F, G)
        From G one edge, to I (C, F)  ****
        From F one edge, to H (C)
    From C, one edge, to E (E)
      From E two edges, to F and G (F, G)
        From G one edge, to I (F) ****
        From F one edge, to H

That means there only two paths from A to I:  
A->B->D->G->I  
A->C->E->G->I