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

general
, , , , ,
1
2

@vijju123

Try this out.

3

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

4

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
5

see this…it’s good !

one part i didn’t understand that why we are adding 1 to our count_Arr instead of count[intermediate]…if you understand it then please help me also :slight_smile:

6

Replying to @pk301 (since it is too long for a comment)

gkcs says that “…we need to find the number of ways to get to 1, multiply that by the number of ways we can get to 2, multiply that by the number of ways to get to 3, and so on and so forth…” and then says that he stores these number of ways in the count array, however this is NOT correct.
If we truly were finding the “number of ways to get to” each vertex, we would be adding count[intermediate]. What we require to find in this problem, and what we are storing in count[v], is not the total number of ways to get to some vertex v, but rather the number of vertices from which we can get to v such that the total distance travelled to v is the shortest possible. I hope it makes sense now.