Optimizing Shortest Paths: Efficient Route Counting with Dijkstra’s Algorithm | 💯✔️
IntuitionThe problem is a variation of the shortest path problem in a weighted graph. Since we need to count the number of ways to reach the destination in the
# Intuition
The problem is a variation of the shortest path problem in a weighted graph. Since we need to count the number of ways to reach the destination in the shortest time, Dijkstra’s algorithm is a natural choice. By tracking both distances and path counts, we can efficiently determine the result.

# Approach
1. **Graph Representation**: Construct an adjacency list from the given roads.
2. **Dijkstra's Algorithm**: Use a min-heap (priority queue) to find the shortest paths from node `0` to all other nodes.
3. **Path Counting**: Maintain an array `ways` where `ways[i]` stores the number of ways to reach node `i` in the shortest time.
4. **Heap Processing**:
   - Pop the node with the smallest distance from the heap.
   - If a shorter path to a neighboring node is found, update its distance and reset the path count.
   - If an equal shortest path is found, add to the existing path count.
5. **Return Result**: The number of ways to reach node `n-1` modulo \(10^9 + 7\).

# Complexity
- **Time Complexity**:  `O(E log V)`, where E is the number of roads and `V` is the number of intersections, due to Dijkstra’s algorithm with a priority queue.
- **Space Complexity**: `O(V + E)` for storing the graph, distances, and path counts.


# Code
```java []
class Solution {
    public int countPaths(int n, int[][] roads) {
        final long inf = Long.MAX_VALUE / 2;
        final int mod = (int) 1e9 + 7;
        long[][] g = new long[n][n];
        for (var e : g) {
            Arrays.fill(e, inf);
        }
        for (var r : roads) {
            int u = r[0], v = r[1], t = r[2];
            g[u][v] = t;
            g[v][u] = t;
        }
        g[0][0] = 0;
        long[] dist = new long[n];
        Arrays.fill(dist, inf);
        dist[0] = 0;
        long[] f = new long[n];
        f[0] = 1;
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 0; j < n; j++) {
                if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            vis[t] = true;
            for (int j = 0; j < n; j++) {
                if (j == t) {
                    continue;
                }
                long ne = dist[t] + g[t][j];
                if (dist[j] > ne) {
                    dist[j] = ne;
                    f[j] = f[t];
                } else if (dist[j] == ne) {
                    f[j] = (f[j] + f[t]) % mod;
                }
            }
        }
        return (int) f[n - 1];
    }
}
```
['Java']