Dijkstra with a Twist: A Beginner-Friendly Editorial Guide to Count Shortest Paths 🛤️😏
Dijkstra with a Twist: A Beginner-Friendly Guide to Count Shortest Paths 🛤️😏Oh look, another graph problem where we need to find the shortest paths—how original
# Dijkstra with a Twist: A Beginner-Friendly Guide to Count Shortest Paths 🛤️😏

Oh look, another graph problem where we need to find the shortest paths—how *original*! 🙄 This time, we’re tasked with counting the number of shortest paths from node 0 to node \(n-1\) in a graph, because apparently just finding the shortest path isn’t enough anymore. We’ll use **Dijkstra’s algorithm** (because of course we will), but with a little twist to count paths. Don’t worry, I’ll hold your hand through this with a beginner-friendly explanation—let’s see if we can make this graph problem less boring! 😏

## Intuition 🕵️‍♀️

When I first saw this problem, I thought: "Great, another shortest path problem—yawn! 🥱 But wait, they want the *number* of shortest paths? That’s… mildly interesting, I guess." Here’s how I broke it down:

- We have a graph with \(n\) nodes (0 to \(n-1\)) and `roads` (edges) where each road \([u, v, t]\) means there’s a path between nodes \(u\) and \(v\) that takes \(t\) time. Oh, and it’s undirected, so the road goes both ways—how convenient! 🚗
- We need to find the number of shortest paths from node 0 to node \(n-1\). A shortest path is a path that takes the least amount of time.
- Normally, Dijkstra’s algorithm would just give us the shortest time to reach each node, but this problem wants us to count how many ways we can get to \(n-1\) using that shortest time. Ugh, extra work! 🙄
- So, we’ll use Dijkstra’s to find the shortest times, but we’ll also keep track of how many paths lead to each node with that shortest time. Sounds like a job for some extra bookkeeping—let’s get to it! 📝

## Approach 🗺️

Here’s how I solved this problem in simple steps—because I know you’re probably new to this and need all the help you can get! 😏 Think of it like planning a road trip where you want the fastest route, but you also want to know how many different fastest routes there are. Let’s break it down:

1. **Build the Graph** 🏗️:
   - First, we need to turn the `roads` into a graph. We’ll use an adjacency list because it’s the *cool* way to store graphs. For each road \([u, v, t]\), add \(v\) to \(u\)’s list and \(u\) to \(v\)’s list, with the time \(t\). So, `adj[u]` will have pairs like \((v, t)\), meaning you can go from \(u\) to \(v\) in \(t\) time. Easy peasy! 🛤️

2. **Set Up for Dijkstra’s** 🛠️:
   - We’re going from node 0 (the source) to node \(n-1\) (the destination). Let’s call them `src` and `dest` because that’s what all the cool kids do. 😎
   - We need two things:
     - `time`: An array to store the shortest time to reach each node. Start with infinity for everyone except the source (set `time[src] = 0`—duh, it takes 0 time to reach the starting point!).
     - `freq`: A map to count the number of shortest paths to each node. Since we start at `src`, set `freq[src] = 1` (there’s exactly 1 way to be at the starting point—by not moving, genius! 🙄).

3. **Run Dijkstra’s with a Twist** 🔄:
   - Use a priority queue to process nodes in order of increasing time (because Dijkstra’s loves to be efficient). Start by pushing \((0, src)\) into the queue (time 0 to reach the source).
   - While the queue isn’t empty:
     - Pop the node with the smallest current time (`currT`) and its node (`node`).
     - If `currT` is greater than the best time we already found for `node` (`time[node]`), skip it—Dijkstra’s doesn’t like wasting time on slow paths! ⏳
     - For each neighbor of `node` (from `adj[node]`):
       - Get the neighbor node (`nbrNode`) and the time to reach it (`edgeT`).
       - **Case 1: Found a Faster Path** 🏎️:
         - If `time[node] + edgeT` is less than `time[nbrNode]`, we’ve found a faster way to reach `nbrNode`! Update `time[nbrNode]` to this new time, set `freq[nbrNode] = freq[node]` (the number of ways to reach `nbrNode` is the same as the number of ways to reach `node`), and push the new time and node into the queue.
       - **Case 2: Found Another Shortest Path** 🛤️:
         - If `time[node] + edgeT` equals `time[nbrNode]`, we’ve found another path to `nbrNode` that takes the same time as the shortest path we already know. Add the number of ways to reach `node` to `freq[nbrNode]` (so `freq[nbrNode] += freq[node]`). Don’t forget to take the modulo because the problem says so—ugh, math! 🙄

4. **Get the Answer** 🎁:
   - After Dijkstra’s finishes, `freq[n-1]` will tell us the number of shortest paths to node \(n-1\). Return it (with modulo, because the problem loves to make us jump through hoops). Done—finally! 🎉

This approach is beginner-friendly because we’re just using Dijkstra’s with a little extra step to count paths. It’s like Dijkstra’s decided to be extra and show off by counting paths too! Let’s see the complexity next. 📊

## Complexity 📈

Let’s figure out how much time and space this solution uses. I’ll explain it in a simple way, but don’t expect me to hold your hand through the math—you’re a big coder now! 😏

- **Time Complexity** ⏱️:
  - **Building the Graph:** We loop through the `roads` list, which has \(E\) edges (where \(E\) is the number of roads). For each edge, we add it to the adjacency list twice (since it’s undirected). That takes **O(E)** time. Not bad! 🛤️
  - **Dijkstra’s Setup:** Initializing the `time` array (size \(n\)) and `freq` map takes **O(n)** time. Pushing the source into the priority queue is **O(1)**—yawn! 🥱
  - **Dijkstra’s Loop:** The priority queue processes each node at most once, so we pop \(n\) nodes. Popping from a priority queue takes **O(log n)** time, so that’s **O(n * log n)** for all nodes. For each node, we look at its neighbors. Across all nodes, we process each edge twice (since the graph is undirected), so that’s \(2E\) edge checks. Each edge check involves a push to the priority queue (which takes **O(log n)** time). So, processing edges takes **O(E * log n)**. Adding it up, Dijkstra’s takes **O(n * log n + E * log n)**, which simplifies to **O((n + E) * log n)**. Oh, and don’t forget the modulo operations—they’re **O(1)** but make us feel fancy! 😎
  - **Overall:** The total time complexity is **O((n + E) * log n)**. Not terrible, I guess! 🕒

- **Space Complexity** 🗄️:
  - **Adjacency List:** The `adj` map stores \(2E\) entries (since each edge is added twice). That’s **O(E)** space.
  - **Priority Queue:** The priority queue can hold up to \(n\) nodes at a time, so that’s **O(n)** space.
  - **Time and Freq Arrays:** The `time` array and `freq` map each take **O(n)** space.
  - **Overall:** Adding it up, we get **O(E + n)** space. Pretty standard for a graph problem—nothing to write home about! 📦

This solution is efficient enough, and the path-counting twist makes it a bit more interesting than plain old Dijkstra’s. Now, let’s see the code—hope you’re ready to be impressed! 😏

![image.png](https://assets.leetcode.com/users/images/a24f791e-76ac-4182-92d3-757be7d1fc6b_1742714501.8926346.png)


## Code 💻

Here’s the C++ code with comments to explain each part. I’ve kept it simple for beginners, but don’t expect me to spoon-feed you every line—you’ve got this! 😎

```cpp []
class Solution {
public: 
    typedef long long ll; // Because typing "long long" is too much work 🙄
    typedef pair<ll, int> P; // Pair of (time, node) for the priority queue
    int mod = 1e9 + 7; // Modulo because the problem loves big numbers

    int countPaths(int n, vector<vector<int>>& roads) {
        // Step 1: Build the graph—because we can’t do anything without it 🏗️
        unordered_map<int, vector<P>> adj; // Adjacency list: node -> (neighbor, time)
        for (auto& e : roads) {
            adj[e[0]].push_back({e[1], e[2]}); // Add edge u -> v
            adj[e[1]].push_back({e[0], e[2]}); // Add edge v -> u (undirected, duh!)
        }
        
        // Step 2: Set up the source and destination 🌍
        int src = 0;
        int dest = n - 1;

        // Step 3: Set up for counting paths 📝
        unordered_map<int, ll> freq; // Number of shortest paths to each node
        freq[src] = 1; // There’s 1 way to reach the source—by standing still, genius!

        // Step 4: Set up Dijkstra’s with a priority queue 🛠️
        priority_queue<P, vector<P>, greater<P>> pq; // Min-heap: (time, node)
        pq.push({0, src}); // Start at source with time 0

        vector<ll> time(n, LLONG_MAX); // Shortest time to reach each node
        time[src] = 0; // It takes 0 time to reach the source—shocking!
        
        // Step 5: Run Dijkstra’s with a twist to count paths 🔄
        while (!pq.empty()) {
            ll currT = pq.top().first; // Current time
            int node = pq.top().second; // Current node
            pq.pop();
            if (currT > time[node]) continue; // Skip if we found a faster path already—Dijkstra’s rules!

            // Check all neighbors of the current node
            for (auto& nbr : adj[node]) {
                int nbrNode = nbr.first; // Neighbor node
                ll edgeT = nbr.second; // Time to reach the neighbor

                // Case 1: Found a faster path to the neighbor 🏎️
                if (time[nbrNode] > time[node] + edgeT) {
                    time[nbrNode] = time[node] + edgeT; // Update shortest time
                    freq[nbrNode] = freq[node]; // Same number of paths as the current node
                    pq.push({time[nbrNode], nbrNode}); // Add to queue to explore further
                }
                // Case 2: Found another path with the same time 🛤️
                else if (time[nbrNode] == time[node] + edgeT) {
                    freq[nbrNode] = (freq[nbrNode] + freq[node]) % mod; // Add the number of paths
                }
            }
        }

        // Step 6: Return the number of shortest paths to the destination 🎉
        return freq[n-1] % mod; // Don’t forget the modulo—because big numbers are scary!
    }
};
```
### 🎉 And that’s it! We’ve solved this graph problem with a beginner-friendly Dijkstra’s approach, added a twist to count paths, and thrown in some sarcasm to keep it spicy. 
### If you’re new to Dijkstra’s or path counting, I hope this guide didn’t bore you to death! If you have any questions, feel free to ask—I might even answer without rolling my eyes! 😜
['Dynamic Programming', 'Graph', 'Shortest Path', 'C++']