Beat 99.5% || Well explained Java Solution with Dijkstra’s Algorithm
This Java program implements Dijkstra’s Algorithm to find the number of shortest paths from node 0 to node n-1 in a weighted undirected graph, where the edges a
This Java program implements **Dijkstra’s Algorithm** to find the **number of shortest paths** from node `0` to node `n-1` in a weighted undirected graph, where the edges are given in the form of a `roads` array.

---

## **Step-by-Step Explanation**

### **1. Understanding the Problem**
- The function `countPaths(int n, int[][] roads)` takes:
  - `n`: The number of nodes (0 to `n-1`).
  - `roads`: A list of edges, where each edge is represented as `[u, v, time]`, meaning there's a bidirectional road between node `u` and node `v` with a travel time of `time`.
- The goal is to determine **how many different shortest paths exist** from node `0` to node `n-1`.

---

### **2. Constants and Data Structures**
```java
final long INF = Long.MAX_VALUE / 2;
final int MOD = (int) 1e9 + 7;
```
- `INF`: Represents an infinitely large number to initialize the graph distances.
- `MOD`: Since the number of paths can be large, we take the result modulo \(10^9 + 7\) to avoid integer overflow.

---

### **3. Initialize the Graph as an Adjacency Matrix**
```java
long[][] graph = new long[n][n];
for (long[] row : graph) {
    Arrays.fill(row, INF);
}
```
- The adjacency matrix `graph[i][j]` represents the travel time between node `i` and node `j`.
- It is initialized with `INF` since initially, no edges are present.

---

### **4. Populate the Graph with Given Roads**
```java
for (int[] road : roads) {
    int u = road[0], v = road[1], time = road[2];
    graph[u][v] = time;
    graph[v][u] = time;
}
```
- Each edge `(u, v, time)` is bidirectional, so `graph[u][v]` and `graph[v][u]` are set to `time`.

---

### **5. Dijkstra’s Algorithm Setup**
```java
long[] dist = new long[n];
Arrays.fill(dist, INF);
dist[0] = 0;

int[] ways = new int[n];
ways[0] = 1;
```
- `dist[i]`: Stores the shortest time to reach node `i` from node `0`.
- `ways[i]`: Stores the **number of shortest paths** to reach node `i` from `0`.
- Initially, `dist[0] = 0` (distance to itself) and `ways[0] = 1` (one way to reach itself).

---

### **6. Priority Queue for Dijkstra’s Algorithm**
```java
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.offer(new Pair(0, 0));
```
- We use a **min-heap (priority queue)** to always process the node with the **smallest known distance**.
- Initially, we add `(0, 0)` meaning **start at node `0` with time `0`**.

---

### **7. Main Loop: Process Nodes in the Priority Queue**
```java
while (!pq.isEmpty()) {
    Pair curr = pq.poll();
    int u = curr.node;
    long time = curr.time;

    if (time > dist[u]) continue;
```
- Extract the node `u` with the smallest `time` from the priority queue.
- If the extracted time is greater than the stored shortest time `dist[u]`, **skip processing** (since a better path has already been found).

---

### **8. Explore All Neighbors of `u`**
```java
for (int v = 0; v < n; v++) {
    if (graph[u][v] == INF) continue;

    long newTime = time + graph[u][v];
```
- Iterate over all nodes `v` to check if there's a direct edge from `u` to `v`.
- Compute `newTime = time + graph[u][v]`, the potential new shortest distance to `v`.

---

### **9. Update Distances and Path Counts**
#### **(a) If `newTime` is shorter, update `dist[v]`**
```java
if (newTime < dist[v]) {
    dist[v] = newTime;
    ways[v] = ways[u];
    pq.offer(new Pair(v, newTime));
}
```
- If we find a **shorter path** to `v`, update `dist[v]` and inherit the number of ways from `ways[u]`.
- Push `(v, newTime)` into the priority queue.

#### **(b) If `newTime` is equal to `dist[v]`, add to the path count**
```java
else if (newTime == dist[v]) {
    ways[v] = (ways[v] + ways[u]) % MOD;
}
```
- If we find **another shortest path** to `v`, increase `ways[v]` by `ways[u]` (modulo `MOD`).

---

### **10. Return the Number of Shortest Paths to `n-1`**
```java
return ways[n - 1];
```
- `ways[n-1]` contains the number of ways to reach the last node `n-1` using the shortest path.

---

## **Helper Class: Pair**
```java
static class Pair implements Comparable<Pair> {
    int node;
    long time;

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

    public int compareTo(Pair other) {
        return Long.compare(this.time, other.time);
    }
}
```
- The `Pair` class stores `(node, time)`.
- Implements `Comparable<Pair>` so that the priority queue **sorts by `time` in ascending order**.

---

## **Time and Space Complexity Analysis**
### **Time Complexity:**
- **Building the graph**: \(O(E)\), where \(E\) is the number of edges.
- **Dijkstra’s Algorithm**:
  - Each node is processed once: \(O(N)\).
  - Each edge is relaxed once: \(O(E)\).
  - The priority queue operations take \(O(\log N)\) time each.
  - Overall, **\(O((N + E) \log N)\) ~ \(O(E \log N)\)**.

### **Space Complexity:**
- **Graph storage**: \(O(N^2)\) (adjacency matrix).
- **Distance and path arrays**: \(O(N)\).
- **Priority queue**: \(O(N)\).
- Overall, **\(O(N^2)\) in the worst case** (due to adjacency matrix).

---

## **Code**
```
class Solution {
    public int countPaths(int n, int[][] roads) {
        final long INF = Long.MAX_VALUE / 2;
        final int MOD = (int) 1e9 + 7;

        // Step 1: Initialize adjacency matrix with INF
        long[][] graph = new long[n][n];
        for (long[] row : graph) {
            Arrays.fill(row, INF);
        }

        // Step 2: Fill the adjacency matrix with given roads
        for (int[] road : roads) {
            int u = road[0], v = road[1], time = road[2];
            graph[u][v] = time;
            graph[v][u] = time;
        }

        // Step 3: Dijkstra’s Algorithm
        long[] dist = new long[n]; // Shortest time to each node
        Arrays.fill(dist, INF);
        dist[0] = 0;

        int[] ways = new int[n]; // Number of shortest paths
        ways[0] = 1;

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.offer(new Pair(0, 0)); // Start from node 0 with time 0

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

            // If we’ve already found a shorter way, skip
            if (time > dist[u]) continue;

            // Step 4: Explore neighbors in the matrix
            for (int v = 0; v < n; v++) {
                if (graph[u][v] == INF) continue; // No direct edge

                long newTime = time + graph[u][v];

                if (newTime < dist[v]) { // Found a shorter path
                    dist[v] = newTime;
                    ways[v] = ways[u]; // Inherit path count
                    pq.offer(new Pair(v, newTime));
                } else if (newTime == dist[v]) { // Found another shortest path
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }

        return ways[n - 1]; // Number of ways to reach node (n-1)
    }

    // Pair class for Priority Queue
    static class Pair implements Comparable<Pair> {
        int node;
        long time;
        public Pair(int node, long time) {
            this.node = node;
            this.time = time;
        }
        public int compareTo(Pair other) {
            return Long.compare(this.time, other.time);
        }
    }
}

```

['Dynamic Programming', 'Graph', 'Heap (Priority Queue)', 'Shortest Path', 'Java']