🎓Wave Relaxation Algorithm Explanation | 5~17ms (Beats 98~100) O(n×(n+m)) | 62.8~65.5 O(n+m)
IntuitionThe problem requires calculating the number of "shortest paths" from the starting node 0 to the destination node n - 1, with the final answer taken mod
# Intuition
The problem requires calculating the number of "shortest paths" from the starting node `0` to the destination node `n - 1`, with the final answer taken modulo $10^9+7$. We can visualize the problem as a map where:

- Each **node (intersection)** represents a junction.
- Each **edge (road)** represents a path connecting two intersections and is associated with a "travel time".

The goal is to determine the shortest travel time from the starting node to the destination and count how many different paths yield that minimum travel time.

---

# Approach
To solve the problem, we adopt the following steps:

### 1. Graph Representation

First, we clearly represent the city's road system:

- **Nodes and Edges**: Use an adjacency list to record which roads are available from each intersection.  
  For example, if it takes `3` units of time to go from intersection `A` to intersection `B`, we record it as:  
  `A → B (3)` and `B → A (3)` (since the roads are bidirectional).

This method allows each node to quickly access its adjacent nodes along with the travel time to reach them.

### 2. Wave Relaxation — Gradually Shortening Distances

The key idea here is to use multiple "waves" (iterations) to gradually update the shortest distance from the starting node to every other node.

#### Why Multiple Waves?
Since the road network might be complex and many potential paths exist, we cannot initially tell which route is the shortest. Therefore, we must repeatedly check and update to ensure we find the truly shortest path.

The specific process is as follows:

- Initially, we set the distance from the starting node (`0`) to itself as `0` (since no movement is required), and all other nodes are set to infinity (indicating that no path has yet been found).
- Then, we perform multiple iterations (waves). In each wave, we traverse every node:
    - For each node, we attempt to propagate (relax) its current known shortest distance to its neighboring nodes.
    - If a new, shorter path is found via this node, update the neighbor’s shortest distance.
    - If the newly found path has the same travel time as the current shortest distance for the neighbor, it indicates that we have found an additional different shortest path; in this case, we add the number of paths from the current node to the neighbor’s path count.
- After processing all nodes in one wave, we check if any node’s distance was updated:
    - If no updates occurred, then all shortest paths have been found and there is no need for further waves.
    - If updates did occur, proceed with the next wave, with a maximum of `n` iterations (since at most `n-1` steps are needed to reach the destination).

#### A Detailed Example:
Assume that the distance from the starting node `0` to node `A` is currently `10`. Now, suppose we find another route from node `B` to node `A` that only takes `8` units of time. 

- We then update the distance for node `A` to `8` and set the number of shortest paths for `A` equal to the number of paths reaching `B` (since this new, shorter path comes through `B`).
- Later, if we discover yet another route that takes `8` minutes to reach node `A`, we add the number of paths provided by this route to node `A`’s total, indicating that there are more ways to reach `A` in the shortest time.

### 3. Accumulating Path Counts and Modulo Operation

Since the number of paths can be very large, we need to perform a modulo operation while accumulating the path counts:

- At every update, we take the modulo $10^9+7$ of the path count to ensure the number stays within the required range and avoids overflow.

---


### Detailed Implementation Steps

#### Step 1: Initialization and Graph Construction

**Building the Graph**: Based on the input `roads` array, convert each edge into an adjacency list representation where each node records its neighboring nodes and the corresponding travel times.

```typescript
const graph: { edges: number[]; weights: number[] }[] = Array.from({ length: n }, () => ({ 
  edges: [],
  weights: [],
}));
for (const [u, v, w] of roads) {
  graph[u].edges.push(v);
  graph[u].weights.push(w);
  graph[v].edges.push(u);
  graph[v].weights.push(w);
}
```

**Initialization of Distances and Path Counts**
- Use an array `dist` to record the shortest distance from the starting node `0` to every other node. Initially, all distances are set to infinity, except for the starting node which is set to `0`.
- Use an array `ways` to record the number of shortest paths for each node. Initially, set the path count for the starting node as `1`.

```typescript
const dist = new Array(n).fill(Infinity);
dist[0] = 0;
const ways = new Array(n).fill(0);
ways[0] = 1;
const MOD = 1000000007;
```

#### Step 2: Wave Relaxation Algorithm

**Performing the Wave Iterations**: To ensure all shortest paths are updated correctly, we perform at most `n` waves. In each wave, traverse all nodes (except the destination) and for each neighboring edge, perform the following:

1. **Relaxation Operation**  
For a given node `node` and its neighbor `neighbor`, calculate: $$newDist = dist[node] + travelTime$$
       
   - If $$newDist < dist[neighbor],$$ update $$dist[neighbor] = newDist$$ and set $$ways[neighbor] = ways[node].$$
   - If $$newDist === dist[neighbor],$$ it means an equivalent shortest path is found; hence, add $$ways[node]$$ to $$ways[neighbor]$$ and perform the modulo operation.

2. **Clearing the Current Node's Path Count**  
To avoid re-propagating the same node’s path count in the same wave, reset $$ways[node]$$ to zero after processing all its adjacent edges.

```typescript
for (let wave = 0; wave < n; wave++) {
  let updated = false; // Indicates whether any update occurred during this wave
  for (let node = 0; node < n - 1; node++) {
    if (ways[node] <= 0) {
      continue;
    }
    const { edges, weights } = graph[node];
    for (let k = 0; k < edges.length; k++) {
      const neighbor = edges[k];
      const newDist = dist[node] + weights[k];
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        ways[neighbor] = ways[node];
        updated = true;
      } else if (newDist === dist[neighbor]) {
        ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
        updated = true;
      }
    }
    ways[node] = 0;
  }
  if (!updated) {
    break;
  }
}
```

#### Step 3: Returning the Result

After the iterations, $$ways[n - 1]$$ represents the total number of shortest paths from the starting node `0` to the destination node `n - 1` (already taken modulo $10^9+7$). Return this as the final answer.

```typescript
return ways[n - 1] % MOD;
```

---

# Complexity
- Time complexity:
  - The wave traversal performs up to `n` iterations. In each iteration, all nodes and their adjacent edges are examined. In the worst-case scenario, the time complexity is $$O(n \times (n + m))$$.
  - In practice, due to the early termination mechanism (breaking out when no updates occur), the algorithm typically does not execute all `n` iterations.
  - **Final time complexity:** $$O(n \times (n + m))$$

- Space complexity:
  - The space is mainly used for the graph representation, and the arrays for distances and path counts, resulting in a space complexity of $$O(n + m)$$.
  - **Final space complexity:** $$O(n + m)$$

---

# Code

```typescript []
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
function countPaths(n: number, roads: number[][]): number {
  if (n === 1) {
    return 1; // Only one node, so one path.
  }
  const MOD = 1000000007;

  // Build the graph where each node stores its neighbors and corresponding travel times.
  const graph: { edges: number[]; weights: number[] }[] = Array.from({ length: n }, () => ({
    edges: [],
    weights: [],
  }));
  for (const [u, v, w] of roads) {
    graph[u].edges.push(v);
    graph[u].weights.push(w);
    graph[v].edges.push(u);
    graph[v].weights.push(w);
  }

  // Initialize arrays for distances and the count of shortest paths.
  const dist = new Array(n).fill(Infinity);
  dist[0] = 0; // Start node has distance 0.
  const ways = new Array(n).fill(0);
  ways[0] = 1; // Only one way to reach the start node.

  // Use wave relaxation: up to n waves are executed.
  for (let wave = 0; wave < n; wave++) {
    let updated = false; // Flag to check if any update happened in this wave.

    // Process all nodes except the destination to propagate their current active path counts.
    for (let node = 0; node < n - 1; node++) {
      // Skip nodes that are not active in this wave (i.e., no new ways to propagate).
      if (ways[node] <= 0) {
        continue;
      }

      // For each neighbor of the current node...
      const { edges, weights } = graph[node];
      for (let k = 0; k < edges.length; k++) {
        const neighbor = edges[k];
        const newDist = dist[node] + weights[k]; // Calculate potential new distance.

        if (newDist < dist[neighbor]) {
          // Found a shorter path: update distance and reset path count.
          dist[neighbor] = newDist;
          ways[neighbor] = ways[node];
          updated = true;
        } else if (newDist === dist[neighbor]) {
          // Found an alternative path with the same distance: accumulate the count.
          ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
          updated = true;
        }
      }
      // Mark the current node as processed in this wave.
      ways[node] = 0;
    }

    // If no updates occurred in the entire wave, the distances and path counts won't change further.
    if (!updated) {
      break;
    }
  }

  // The count of shortest paths to the destination node is returned.
  return ways[n - 1] % MOD;
}

```
```javascript []
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
function countPaths(n, roads) {
  if (n === 1) {
    return 1; // Only one node, so one path.
  }
  const MOD = 1000000007;

  // Build the graph where each node stores its neighbors and corresponding travel times.
  const graph = Array.from({ length: n }, () => ({
    edges: [],
    weights: [],
  }));
  for (const [u, v, w] of roads) {
    graph[u].edges.push(v);
    graph[u].weights.push(w);
    graph[v].edges.push(u);
    graph[v].weights.push(w);
  }

  // Initialize arrays for distances and the count of shortest paths.
  const dist = new Array(n).fill(Infinity);
  dist[0] = 0; // Start node has distance 0.
  const ways = new Array(n).fill(0);
  ways[0] = 1; // Only one way to reach the start node.

  // Use wave relaxation: up to n waves are executed.
  for (let wave = 0; wave < n; wave++) {
    let updated = false; // Flag to check if any update happened in this wave.

    // Process all nodes except the destination to propagate their current active path counts.
    for (let node = 0; node < n - 1; node++) {
      // Skip nodes that are not active in this wave (i.e., no new ways to propagate).
      if (ways[node] <= 0) {
        continue;
      }

      // For each neighbor of the current node...
      const { edges, weights } = graph[node];
      for (let k = 0; k < edges.length; k++) {
        const neighbor = edges[k];
        const newDist = dist[node] + weights[k]; // Calculate potential new distance.

        if (newDist < dist[neighbor]) {
          // Found a shorter path: update distance and reset path count.
          dist[neighbor] = newDist;
          ways[neighbor] = ways[node];
          updated = true;
        } else if (newDist === dist[neighbor]) {
          // Found an alternative path with the same distance: accumulate the count.
          ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
          updated = true;
        }
      }
      // Mark the current node as processed in this wave.
      ways[node] = 0;
    }

    // If no updates occurred in the entire wave, the distances and path counts won't change further.
    if (!updated) {
      break;
    }
  }

  // The count of shortest paths to the destination node is returned.
  return ways[n - 1] % MOD;
}

```

# Result

![image.png](https://assets.leetcode.com/users/images/c4e883f5-3770-4ad9-8e49-a5e325b8a2f1_1742721235.4290886.png)

![image.png](https://assets.leetcode.com/users/images/ec6a6a46-a5b9-4493-bd1c-8e075c723474_1742721259.538926.png)

['Dynamic Programming', 'Graph', 'Shortest Path', 'TypeScript', 'JavaScript']