asked 20 Aug '17, 11:38

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+Vlog 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. answered 20 Aug '17, 19:40

https://www.youtube.com/watch?v=rBvFMJLYAbs 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 :) answered 20 Aug '17, 20:06

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. answered 21 Aug '17, 04:58

@vijju123
Try this out.
Its out of my scope atm dear. I am yet to implement djikstra.