1976. Number of Ways to Arrive at Destination

Problem Statement

You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer n and an array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.

Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 10^9 + 7.

Examples

Example 1:

Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➜ 1 ➜ 2 ➜ 5 ➜ 6
- 0 ➜ 1 ➜ 3 ➜ 5 ➜ 6
- 0 ➜ 4 ➜ 6
- 0 ➜ 6

Example 2:

Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.

Constraints

1 <= n <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= ui, vi <= n - 1
1 <= timei <= 10^9
ui != vi
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Graph structure: What is the graph structure? (Assumption: Undirected weighted graph - roads connect intersections with travel times)
Optimization goal: What are we optimizing for? (Assumption: Shortest path from intersection 0 to intersection n-1)
Path counting: What should we count? (Assumption: Number of different shortest paths from 0 to n-1)
Return value: What should we return? (Assumption: Integer - number of shortest paths modulo 10^9 + 7)
Path uniqueness: What makes paths different? (Assumption: Different sequences of intersections - same length but different routes)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Use DFS to explore all paths from node 0 to node n-1. Keep track of the current path and total time. When reaching node n-1, record the time. After exploring all paths, find the minimum time and count how many paths have that minimum time. This approach has exponential time complexity O(2^V) in worst case, which is too slow for graphs with many nodes.

Step 2: Semi-Optimized Approach (7 minutes)

Use BFS with distance tracking: perform BFS from node 0, tracking the shortest distance to each node. When multiple paths reach a node with the same distance, increment a counter. However, BFS only works for unweighted graphs. For weighted graphs, we need Dijkstra’s algorithm. Use Dijkstra’s to find shortest distances, then use DFS or DP to count paths with shortest distance. This requires two passes and careful implementation.

Step 3: Optimized Solution (8 minutes)

Combine Dijkstra’s algorithm with path counting in a single pass: use a priority queue to find shortest paths, maintaining both shortestTime[i] (shortest distance) and pathCount[i] (number of shortest paths). When exploring neighbors, if we find a shorter path, update the distance and reset the count. If we find an equal path, accumulate the count. This achieves O((V + E) log V) time complexity, which is optimal for finding shortest paths in weighted graphs. The key insight is that we can count paths during Dijkstra’s execution by tracking how many ways we can reach each node with the shortest distance.

Solution Approach

This problem requires finding the number of shortest paths from node 0 to node n-1 in a weighted, undirected graph. This is a classic application of Dijkstra’s algorithm combined with dynamic programming to count paths.

Key Insights:

Dijkstra’s Algorithm: Find shortest distances from source (node 0) to all nodes
Path Counting: Count number of ways to reach each node with shortest distance
Multiple Paths: When multiple paths have the same shortest distance, accumulate the count
Modulo Arithmetic: Handle large numbers with 10^9 + 7

Algorithm:

Build adjacency list: Create graph representation from roads
Dijkstra’s Algorithm: Use priority queue to find shortest paths
Path Counting:
- If shorter path found: update distance and reset count
- If equal path found: add to count
Return: Number of shortest paths to destination

Solution

Solution: Dijkstra’s Algorithm with Path Counting

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        const int MOD = 1e9 + 7;
        vector<vector<pair<int, int>>> adjList(n);
        for(auto& road: roads) {
            int startNode = road[0], endNode = road[1], travelTime = road[2];
            adjList[startNode].emplace_back(endNode, travelTime);
            adjList[endNode].emplace_back(startNode, travelTime);
        }
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> minHeap;
        vector<long long> shortestTime(n, LLONG_MAX);
        vector<int> pathCount(n, 0);
        shortestTime[0] = 0;
        pathCount[0] = 1;
        minHeap.emplace(0, 0);
        while(!minHeap.empty()) {
            auto [currTime, currNode] = minHeap.top();
            minHeap.pop();

            if(currTime > shortestTime[currNode]) continue;
            for(auto& [neighborNode, roadTime]: adjList[currNode]) {
                if(currTime + roadTime < shortestTime[neighborNode]) {
                    shortestTime[neighborNode] = currTime + roadTime;
                    pathCount[neighborNode] = pathCount[currNode];
                    minHeap.emplace(shortestTime[neighborNode], neighborNode);
                }
                else if (currTime + roadTime == shortestTime[neighborNode]) {
                    pathCount[neighborNode] = (pathCount[neighborNode] + pathCount[currNode]) % MOD;
                }
            }
        }
        return pathCount[n - 1];
    }
};

Algorithm Explanation:

Graph Construction (Lines 5-9):
- Build bidirectional adjacency list
- Each edge stores (neighbor, weight)
Initialization (Lines 10-15):
- shortestTime[i]: Shortest time to reach node i (initialized to LLONG_MAX)
- pathCount[i]: Number of shortest paths to node i (initialized to 0)
- Start node: shortestTime[0] = 0, pathCount[0] = 1
- Priority queue: (time, node) pairs, min-heap
Dijkstra’s Algorithm (Lines 16-30):
- Extract node with minimum time
- Skip if outdated (already found shorter path)
- For each neighbor:
  - Shorter path found: Update distance and reset count
  - Equal path found: Add to count (modulo)
Result: Return pathCount[n-1] - number of shortest paths to destination

Example Walkthrough:

For n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]:

Graph:
0 --2-- 1 --3-- 2
|       |       |
7       3       1
|       |       |
6 --1-- 5 --1-- 3
|       |
2       1
|
4

Dijkstra's Execution:

Step 1: Start at node 0
- shortestTime[0] = 0, pathCount[0] = 1
- Explore: 0→1 (time=2), 0→4 (time=5), 0→6 (time=7)

Step 2: Process node 1 (time=2)
- shortestTime[1] = 2, pathCount[1] = 1
- Explore: 1→2 (time=2+3=5), 1→3 (time=2+3=5)

Step 3: Process node 4 (time=5)
- shortestTime[4] = 5, pathCount[4] = 1
- Explore: 4→6 (time=5+2=7)

Step 4: Process node 2 (time=5)
- shortestTime[2] = 5, pathCount[2] = 1
- Explore: 2→5 (time=5+1=6)

Step 5: Process node 3 (time=5)
- shortestTime[3] = 5, pathCount[3] = 1
- Explore: 3→5 (time=5+1=6), 3→6 (time=5+3=8)

Step 6: Process node 5 (time=6)
- shortestTime[5] = 6, pathCount[5] = 2 (from node 2 and 3)
- Explore: 5→6 (time=6+1=7)

Step 7: Process node 6 (time=7)
- Found paths with time=7:
  - 0→6 (direct): pathCount = 1
  - 0→4→6: pathCount = 1
  - 0→1→2→5→6: pathCount = 1
  - 0→1→3→5→6: pathCount = 1
- pathCount[6] = 1 + 1 + 1 + 1 = 4

Result: 4 ways to reach node 6 with shortest time 7

Dijkstra’s Template

Here’s the general template for Dijkstra’s algorithm with path counting:

int countShortestPaths(int n, vector<vector<pair<int, int>>>& adjList, int start, int end) {
    const int MOD = 1e9 + 7;
    const long long INF = LLONG_MAX;
    
    // Distance and path count arrays
    vector<long long> dist(n, INF);
    vector<int> pathCount(n, 0);
    
    // Priority queue: (distance, node)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    
    // Initialize start node
    dist[start] = 0;
    pathCount[start] = 1;
    pq.emplace(0, start);
    
    while (!pq.empty()) {
        auto [currDist, currNode] = pq.top();
        pq.pop();
        
        // Skip if outdated (already found shorter path)
        if (currDist > dist[currNode]) continue;
        
        // Explore neighbors
        for (auto& [neighbor, weight] : adjList[currNode]) {
            long long newDist = currDist + weight;
            
            // Found shorter path: update distance and reset count
            if (newDist < dist[neighbor]) {
                dist[neighbor] = newDist;
                pathCount[neighbor] = pathCount[currNode];
                pq.emplace(newDist, neighbor);
            }
            // Found equal path: add to count
            else if (newDist == dist[neighbor]) {
                pathCount[neighbor] = (pathCount[neighbor] + pathCount[currNode]) % MOD;
            }
        }
    }
    
    return pathCount[end];
}

Key Template Components:

Data Structures:
- dist[i]: Shortest distance to node i
- pathCount[i]: Number of shortest paths to node i
- Priority queue: Min-heap for Dijkstra’s
Initialization:
- Start node: dist[start] = 0, pathCount[start] = 1
- All other nodes: dist[i] = INF, pathCount[i] = 0
Main Loop:
- Extract minimum distance node
- Skip outdated entries
- Update neighbors:
  - Shorter: Update distance, reset count
  - Equal: Accumulate count
Modulo: Apply MOD to prevent overflow

Complexity Analysis

Time Complexity: O((V + E) log V)

Priority queue operations: O(E log V) - each edge processed once
Graph traversal: O(V + E) - visit all nodes and edges
Total: O((V + E) log V) where V = n, E = number of roads

Space Complexity: O(V + E)

Adjacency list: O(E) - store all edges
Distance array: O(V) - store distances for all nodes
Path count array: O(V) - store counts for all nodes
Priority queue: O(V) - at most V nodes in queue
Total: O(V + E)

Key Points

Dijkstra’s Algorithm: Finds shortest paths in weighted graphs with non-negative edges
Path Counting: Track number of ways to reach each node with shortest distance
Multiple Paths: When multiple paths have same distance, accumulate counts
Modulo Arithmetic: Handle large numbers with 10^9 + 7
Bidirectional Graph: Roads are undirected (both directions)
Outdated Skip: Skip nodes with outdated distances in priority queue

Alternative Approaches

Approach 1: Dijkstra + DP (Current Solution)

Time: O((V + E) log V)
Space: O(V + E)
Best for: General graphs with non-negative weights

Approach 2: BFS (Unweighted Graphs Only)

Time: O(V + E)
Space: O(V + E)
Limitation: Only works for unweighted graphs

Approach 3: Floyd-Warshall (All Pairs)

Time: O(V³)
Space: O(V²)
Use case: Need shortest paths between all pairs

743. Network Delay Time - Dijkstra’s basic application
1631. Path With Minimum Effort - Dijkstra’s on grid
1514. Path with Maximum Probability - Modified Dijkstra’s
787. Cheapest Flights Within K Stops - Dijkstra’s with constraints

Robina Li

1976. Number of Ways to Arrive at Destination

1976. Number of Ways to Arrive at Destination

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approach

Key Insights:

Algorithm:

Solution

Solution: Dijkstra’s Algorithm with Path Counting

Algorithm Explanation:

Example Walkthrough:

Dijkstra’s Template

Key Template Components:

Complexity Analysis

Time Complexity: O((V + E) log V)

Space Complexity: O(V + E)

Key Points

Alternative Approaches

Approach 1: Dijkstra + DP (Current Solution)

Approach 2: BFS (Unweighted Graphs Only)

Approach 3: Floyd-Warshall (All Pairs)

Tags

Related Posts

Recent Posts

1976. Number of Ways to Arrive at Destination

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approach

Key Insights:

Algorithm:

Solution

Solution: Dijkstra’s Algorithm with Path Counting

Algorithm Explanation:

Example Walkthrough:

Dijkstra’s Template

Key Template Components:

Complexity Analysis

Time Complexity: O((V + E) log V)

Space Complexity: O(V + E)

Key Points

Alternative Approaches

Approach 1: Dijkstra + DP (Current Solution)

Approach 2: BFS (Unweighted Graphs Only)

Approach 3: Floyd-Warshall (All Pairs)

Related Problems

Tags

Related Posts

Recent Posts