Dijkstra’s Made Easy | Interview-Ready Solution with Intuitive Explanation
IntuitionTo solve this problem, we need to find the shortest path, which naturally suggests using Dijkstra’s algorithm. Additionally, we need to count the numbe
# Intuition
To solve this problem, we need to find the shortest path, which naturally suggests using Dijkstra’s algorithm. Additionally, we need to count the number of ways to reach the destination using the shortest path. Every time we encounter a minimum distance, we accumulate the number of ways we reached that node. If we find another path with the same minimum distance, we sum up the ways from both paths (similar to a DP-based accumulation).

# Approach
- Build the graph using an adjacency list.
- Use a priority queue (min-heap) to process nodes based on the shortest distance.
- Initialize the queue with the source node and a distance of 0: (0, source).
- Maintain a dist array to store the shortest distance from the source to each node. Initialize it to a large value except for the source, which is 0.
- Maintain a ways array to count the number of shortest paths to each node. Set countWays[source] = 1.
- Process nodes in the priority queue:
- If we find a shorter path to a node, update dist[node] and reset countWays [node] with countWays[parent].
- If we find an alternate path with the same minimum distance, add countWays[parent] to countWays[node].
- Return countWays[destination], which gives the number of ways to reach the destination using the shortest path.

# Complexity
- Time complexity: O(ElogV)

- Space complexity: O(E+V)

# Code
```java []
class Solution {
    public int countPaths(int n, int[][] roads) {

        // build graph
        List<int[]>[] graph = new LinkedList[n];

        for(int i = 0; i < n; i++) {
            graph[i] = new LinkedList<>();
        }

        for(int[] road : roads) {
            int x = road[0];
            int y = road[1];
            int cost = road[2];
            graph[x].add(new int[]{y, cost});
            graph[y].add(new int[]{x, cost});
        }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        dist[0] = 0;
        
        // cost, start node
        pq.offer(new int[]{0, 0});
        int[] countWays = new int[n];
        countWays[0] = 1;
        while(!pq.isEmpty()) {
            int[] poll = pq.poll();
            int curr = poll[1];
            int cost = poll[0];
            if(curr == n-1) {
                //System.out.println(Arrays.toString(count));
                //System.out.println(Arrays.toString(dist));
                return countWays[curr];
            }
            for(int[] next : graph[curr]) {
                int dest = next[0];
                int newCost = next[1];
                if(cost + newCost < dist[dest]) {
                    dist[dest] = cost + newCost;
                    pq.offer(new int[]{cost + newCost, dest});
                    countWays[dest] = countWays[curr];
                } else if(cost + newCost == dist[dest]) {
                    //System.out.println(dist[dest] +" " + curr + " " + dest);
                    countWays[dest] = (countWays[dest] + countWays[curr])%1000000007;
                }
            }
        }
        
        return -1;
    }
}
```


*If you find helpful, Please Upvote 🙏 
['Dynamic Programming', 'Graph', 'Shortest Path', 'Java']