# how to solve this problem based on graph and counting from hackerearth?

@vijju123

Try this out.

Its out of my scope atm dear. I am yet to implement djikstra.

Hey @arpit728,

It’s clear that we need to use Dijkstra’s algorithm to solve this problem because Dijkstra’s algorithm finds the shortest distance from the root to other nodes in O(|E|+|V|log |V|) time. But the question asks us to find the number of ways path can be chosen.

Now when you are applying Dijkstra’s algorithm, we have to take another variable array where we are going to store the number of paths we have come across with the smallest path. After we know what is the number of paths required to reach each node than applying the rule of multiplication in combination. Multiply all the values in the array.

let’s take an example:

1->2 1

2->3 3

1->3 2

so now when we start applying Dijkstra’s algo from index 1 other distances are infinite, now mark index 1 as visited and index 2 is at distance of 1 and index 3 is at a distance of 2 from 1. so our array would be 1, and then we go to 2 and than again min distance to 3 is same before so we increase the value of array to 2. at last 3 is also visited.

array - [1,1,2]

multiply all the values and you get the answer as 2

Hope this helps!

Pre requisite- Dijkstra’s algorithm.

2 Likes

see this…it’s good !