Naive Approach

A brute force approach would involve exploring all possible paths from the starting intersection to the destination intersection. We could use a recursive depth-first search (DFS) to enumerate all paths and calculate the time taken for each path. We'd keep track of the shortest time found so far and the number of paths that achieve that shortest time.

This approach, however, suffers from exponential time complexity as the number of paths can grow very quickly with the number of intersections and roads. It is also prone to stack overflow errors for larger graphs because of the recursive nature of DFS.

Optimal Approach: Dijkstra's Algorithm with Path Counting

A more efficient solution can be achieved using Dijkstra's algorithm to find the shortest paths and simultaneously count the number of shortest paths. Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest-path tree.

Here's how we can adapt Dijkstra's algorithm:

1. Initialization:

   • dist[i] stores the shortest distance from the starting intersection (0) to intersection i. Initialize dist[0] to 0 and all other dist[i] to infinity.
   • ways[i] stores the number of shortest paths from the starting intersection (0) to intersection i. Initialize ways[0] to 1 and all other ways[i] to 0.
   • Use a priority queue (min-heap) to store vertices to be visited, prioritized by their distance from the starting intersection.

2. Iteration:

   • While the priority queue is not empty:
     • Extract the intersection u with the smallest distance from the priority queue.
     • For each neighbor v of u:
       • If dist[u] + time(u, v) < dist[v]:
         • Update dist[v] = dist[u] + time(u, v). This means we found a shorter path to v.
         • Set ways[v] = ways[u]. The number of shortest paths to v is now the same as the number of shortest paths to u.
         • Add v to the priority queue.
       • Else if dist[u] + time(u, v) == dist[v]:
         • Increment ways[v] by ways[u]. This means we found another shortest path to v. We add the number of shortest paths to u because any shortest path to u can be extended to v with the same total distance.

3. Result:

   • After Dijkstra's algorithm finishes, ways[n-1] will contain the number of shortest paths from intersection 0 to intersection n-1.
   • Take modulo 10^9 + 7 to avoid integer overflow.

Edge Cases

• Single Intersection: If n = 1, there's only one intersection, and the number of ways is 1.
• No Roads: If roads is empty and n > 1, there is no path from 0 to n-1, although the problem states that all intersections are reachable. Ensure this constraint holds during input validation.
• Large time values: The time values in roads can be large, so use long datatype in the priority queue. Also use long type for storing intermediate distances to avoid integer overflow.

Code

import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        List<List<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] road : roads) {
            int u = road[0];
            int v = road[1];
            int time = road[2];
            adj.get(u).add(new Pair(v, time));
            adj.get(v).add(new Pair(u, time));
        }

        long[] dist = new long[n];
        long[] ways = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        ways[0] = 1;

        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingLong(p -> p.time));
        pq.offer(new Pair(0, 0));

        int MOD = (int) 1e9 + 7;

        while (!pq.isEmpty()) {
            Pair curr = pq.poll();
            int u = curr.node;
            long d = curr.time;

            if (d > dist[u]) continue;  // Optimization: Skip if we've already found a shorter path to u

            for (Pair neighbor : adj.get(u)) {
                int v = neighbor.node;
                long time = neighbor.time;

                if (dist[u] + time < dist[v]) {
                    dist[v] = dist[u] + time;
                    ways[v] = ways[u];
                    pq.offer(new Pair(v, dist[v]));
                } else if (dist[u] + time == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }

        return (int) ways[n - 1];
    }

    static class Pair {
        int node;
        long time;

        public Pair(int node, long time) {
            this.node = node;
            this.time = time;
        }
    }
}

Big O Runtime and Space Complexity

• Time Complexity: O(E log V), where E is the number of roads (edges) and V is the number of intersections (vertices). This is because Dijkstra's algorithm with a priority queue takes O(E log V) time.
• Space Complexity: O(V + E), where V is the number of intersections and E is the number of roads. We use O(V) space for the dist and ways arrays, and O(E) space to store the adjacency list.