Do networks bother you?

We’ll try to find out the total number of ways to reach a destination from a source for any given network.

In how many ways can you reach the Destination from the Source as shown in the network above?

Pretty easy. Right?

Total of 4 ways. Quite clear from the diagram.

• Start - A - C - D - E - G - Destination
• Start - A - C - D - F - G - Destination
• Start - B - C - D - E - G - Destination
• Start - B - C - D - F - G - Destination

For this diagram, it was easy to visualize all the paths from Source to Destination.

But, what if the diagram is:

or, increasing the complexity a bit further:

Would you still be able to picture out all of the possible paths for the given diagram?

We need utmost care to not possibly miss any of the paths, if we go on counting all of the paths in the network.

Let’s figure out a simple process by which we’ll able to find out the total number of paths to reach a destination from a source for any given network, however complex it may be.

For all the nodes we need to fetch the following information:

• Total incoming paths to a Node

And, the steps are:

1. Calculate total incoming paths to any node

2. Outgoing paths will contain a value which is the sum of all the incoming paths

3. So, all subsequent nodes from N can be reached by the sum of the number of all the incoming paths.

4. And, last but the most important point to consider: We’ll always assume that the total number of ways to reach our source node is 1. So, all the outgoing paths from source will start with value 1.

That’s it.

Enough of concepts.

Let’s get down with solving the networks we saw earlier.

Problem 1:

Find the total number of ways to reach Destination from Source.

Total incoming paths to B = 1 (As all the paths emanating from Source contain value 1)

Therefore, Outgoing paths from B = 1

Total incoming paths to E = 1

Therefore, Outgoing paths from E = 1

Total incoming paths to D = 1+1+1 = 3

Therefore, Outgoing paths from D = 3

Total incoming paths to C = 1+3 = 4

Therefore, Outgoing paths from C = 4

Total incoming paths to F = 3+1 = 4

Therefore, Outgoing paths from F = 4

So, Total number of ways to reach Destination = From C + From D + From F = 4+3+4 = 11

So, a total of 11 ways to reach the Destination from Source.

Problem 2:

Find the total number of ways to reach Destination from Source.

Total incoming paths to B = 1

Therefore, Outgoing paths from B = 1

Total incoming paths to G = 1

Therefore, Outgoing paths from G = 1

Total incoming paths to E = 1+1+1 = 3

Therefore, Outgoing paths from E = 3

Total incoming paths to C = 1+3 = 4

Therefore, Outgoing paths from C = 4

Total incoming paths to H = 3+1 = 4

Therefore, Outgoing paths from H = 4

Total incoming paths to F = 4+4+3 = 11

Therefore, Outgoing paths from F = 11

Total incoming paths to D = 4+11 = 15

Therefore, Outgoing paths from D = 15

Total incoming paths to I = 4+11 = 15

Therefore, Outgoing paths from I = 15

So, Total number of ways to reach Destination = From D + From F + From I = 15+11+15 = 41

So, a total of 41 ways to reach the Destination from Source.

Hope, problems from networks don’t become a problem for us in future. :)

Cheers.