Graph - DSA: Number of Ways to Arrive at Destination

1. Problem Statement & Context Overview

When studying shortest-path algorithms like Dijkstra's, the objective is typically to find the minimum distance from a source node to a destination node in a weighted graph. However, a fascinating variant of this problem asks: In how many unique shortest paths can you travel from the source node ($0$) to the destination node ($n - 1$)?

• Graph Characteristics: Undirected, zero-indexed graph with $n$ intersections (nodes) numbered from $0$ to $n-1$, connected by weighted roads.
• Goal: Find the total number of distinct paths between source $0$ and destination $n-1$ that share the exact same minimum travel time.
• Constraint: Results can be large, so all way-counting additions must be computed modulo $10^9 + 7$.

2. Core Mental Model & Why Naive Intuition Fails

The Naive Counting Fallacy

A common initial intuition is: "Whenever a Dijkstra traversal reaches the destination node with the shortest distance, increment a global counter by 1."

Consider a scenario where multiple branches merge into a node before reaching the destination:

• If Node $X$ can be reached via 2 different paths, and Node $Y$ via 1 path, both leading to Node $Z$ with the same shortest distance, simply counting "arrivals" ignores the fact that Node $X$ itself represents multiple underlying paths.
• The Correct Rule: To find the number of ways to reach a node, you must sum up the ways accumulated from all incoming precursor nodes that successfully deliver the minimum distance.

3. Data Structures & Initialization Configuration

To adapt Dijkstra's algorithm to track path counts alongside minimum distances, three core data structures are required:

1. Priority Queue (std::priority_queue): Stores pairs of (distance, node) ordered as a min-heap to always process the currently known shortest path.
2. Distance Array (dist[]): Initializes all node distances to infinity ($\infty$), except the source node which is set to $0$.
3. Ways Array (ways[]): Initializes all node path counts to $0$, except the source node (ways[0] = 1), indicating exactly one way to start at the origin.

4. Step-by-Step Algorithm Evolution & Logic Branches

When expanding from a current node to an adjacent neighbor (adjNode) via an edge of weight edW, we evaluate two major conditional branches:

Case A: First Time Discovered (Strictly Shorter Distance)

If the newly calculated distance (dist[node] + edW) is strictly less than the currently recorded dist[adjNode]:

1. Update dist[adjNode] = dist[node] + edW.
2. Reset or overwrite the path count: ways[adjNode] = ways[node].
3. Push the new state (dist[adjNode], adjNode) into the priority queue.

Case B: Alternative Path with Equal Minimum Distance

If the newly calculated distance matches the existing dist[adjNode] exactly (dist[node] + edW == dist[adjNode]):

1. Do not modify the distance.
2. Accumulate the ways: ways[adjNode] = (ways[adjNode] + ways[node]) % MOD.
3. Do not push duplicate states into the priority queue (to prevent redundant processing loops).

5. Complete Step-by-Step Dry Run Example

Imagine a graph where source is 0 and we evaluate transitions:

1. Pop (0, 0) from Priority Queue:
   • dist[0] = 0, ways[0] = 1.
   • Explore neighbors 1, 2, 3, 4. All are updated (Case A) with distances and ways = 1.
2. Process Node 1 (dist = 1, ways = 1):
   • Explores neighbor 5. Updates dist[5] = 3, ways[5] = 1.
3. Process Node 3 (dist = 1, ways = 1):
   • Explores neighbor 5 with edge weight 2 (total distance = $1 + 2 = 3$).
   • Since dist[5] is already 3, this triggers Case B:

4. Subsequent Merges: Every time an existing minimal distance is rediscovered, its ways count accumulates the precursor node's ways, flawlessly capturing complex branching topologies.

6. Production-Ready C++ Implementation

Below is the complete, optimized C++ solution utilizing Dijkstra's algorithm with path counting and modulo arithmetic:

#include <bits/stdc++.h>
using class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        // Step 1: Create adjacency list (undirected graph storing {neighbor, weight})
        vector<vector<pair<int, int>>> adj(n);
        for (auto& road : roads) {
            int u = road[0];
            int v = road[1];
            int wt = road[2];
            adj[u].push_back({v, wt});
            adj[v].push_back({u, wt});
        }

        // Step 2: Initialize Priority Queue, Distance array, and Ways array
        // Min-heap storing pairs of {distance, node}
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

        vector<long long> dist(n, 1e18);
        vector<long long> ways(n, 0);

        dist[0] = 0;
        ways[0] = 1;
        pq.push({0, 0});

        long long mod = 1e9 + 7;

        // Step 3: Dijkstra's Traversal Loop
        while (!pq.empty()) {
            auto it = pq.top();
            pq.pop();
            long long dis = it.first;
            int node = it.second;

            // Iterate through all adjacent neighbors
            for (auto& neighbor : adj[node]) {
                int adjNode = neighbor.first;
                long long edW = neighbor.second;

                // Case A: This is the first time we're finding a shorter path
                if (dis + edW < dist[adjNode]) {
                    dist[adjNode] = dis + edW;
                    ways[adjNode] = ways[node];
                    pq.push({dist[adjNode], adjNode});
                }
                // Case B: We found another path with the exact same shortest distance
                else if (dis + edW == dist[adjNode]) {
                    ways[adjNode] = (ways[adjNode] + ways[node]) % mod;
                }
            }
        }

        // Return the number of ways to reach destination (n - 1) modulo 1e9 + 7
        return ways[n - 1] % mod;
    }
};

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(E \log V)$, where $E$ is the number of roads (edges) and $V$ is the number of intersections (nodes). This mirrors standard Dijkstra's algorithm because updating path counts takes $\mathcal{O}(1)$ time per edge relaxation, and each node/edge is pushed into the priority queue at most once per minimal distance discovery.
• Space Complexity: $\mathcal{O}(V + E)$ to store the adjacency list graph representation, alongside $\mathcal{O}(V)$ auxiliary storage for the distance array, ways array, and priority queue stack frames.

8. Summary and Key Takeaways

• Problem Distinction: Finding the number of shortest paths differs from finding just the shortest distance; it requires counting combinatorial paths rather than a single traversal outcome.
• Flawed Naive Approach: Simply counting how many times the destination is reached inside Dijkstra's loop fails because intermediate nodes can themselves be reached via multiple paths.
• The Accumulation Rule: When a neighbor is reached with a matching minimum distance (dis + edW == dist[adjNode]), add the parent node's ways count (ways[node]) to the neighbor's ways count (ways[adjNode]).
• State Initialization: Always initialize dist[0] = 0 and ways[0] = 1, with all other distances set to infinity and ways set to 0.
• Modulo Safety: Apply 1e9 + 7 modulo operations whenever accumulating path sums to prevent integer overflow during competitive programming evaluations.
• Efficiency: Retains the optimal $\mathcal{O}(E \log V)$ time efficiency of Dijkstra's algorithm while seamlessly solving complex directed or undirected counting graphs.