✅✅ Dijkstra's Algorithm || Beginner Friendly || Easiest Code
Approach1. Graph Representation
The given graph is an undirected weighted graph.
Construct an adjacency list adj using an unordered map.
2. Dijkstra’s Algorithm
# Approach

### **1. Graph Representation**
- The given graph is an **undirected weighted graph**.
- Construct an **adjacency list** `adj` using an unordered map.

### **2. Dijkstra’s Algorithm**
- **Priority queue (Min-Heap)** is used to always process the node with the smallest distance first.
- Maintain a **`time[]`** array to store the shortest time to reach each node.
- Maintain a **`pathCount[]`** array to store the number of ways to reach each node with the shortest path.

### **3. Processing Nodes**
- Start from **node `0`**, set `time[0] = 0` and `pathCount[0] = 1`.
- For each adjacent node:
  - If a **shorter path** is found, update `time[]` and reset `pathCount[]`.
  - If an **equally short path** is found, add the number of ways to reach the current node (`pathCount[curr]`).
  
### **4. Modulo Operations**
- Since the number of paths can be large, **take modulo `1e9 + 7`** in calculations.

# Complexity Analysis
- **Time Complexity:**  
  - **`O((N + E) log N)`** (Dijkstra with min-heap).
- **Space Complexity:**  
  - **`O(N + E)`** (Adjacency list + Priority queue + Distance/Path arrays).

# 🔹 Edge Cases Considered
 - ✔ Graph with **no roads** (only one node).  
- ✔ Graph with **multiple shortest paths**.  
- ✔ Graph with **large constraints** (to test efficiency of Dijkstra).  
- ✔ **Disconnected nodes** (ensures no invalid access).  

🚀 **Dijkstra ensures optimal paths, and path counting is done efficiently!**

# Code
```cpp []
class Solution {
public:
    const int MOD=1e9+7;
    typedef pair<long long,int>P;
    int countPaths(int n, vector<vector<int>>& roads) {
        unordered_map<int,vector<pair<int,int>>>adj;

        for(auto &vec:roads){
            int u=vec[0];
            int v=vec[1];
            int w=vec[2];

            adj[u].push_back({v,w});
            adj[v].push_back({u,w});
        }

        priority_queue<P,vector<P>,greater<P>>pq;
        vector<long long>time(n,LLONG_MAX);
        vector<int>pathCount(n,0);

        time[0]=0;
        pathCount[0]=1;
        pq.push({0,0});

        while(!pq.empty()){
            long long currDist=pq.top().first;
            int currNode=pq.top().second;
            pq.pop();

            for(auto &ngbr:adj[currNode]){
                int ngbrNode=ngbr.first;
                int ngbrDist=ngbr.second;

                if(currDist+ngbrDist<time[ngbrNode]){
                    time[ngbrNode]=currDist+ngbrDist;
                    pq.push({currDist+ngbrDist,ngbrNode});
                    pathCount[ngbrNode]=pathCount[currNode];
                }
                else if(currDist+ngbrDist==time[ngbrNode]){
                    pathCount[ngbrNode]=(pathCount[ngbrNode]+pathCount[currNode])%MOD;
                }
            }
        }
        return pathCount[n-1];
    }
};
```
# Have a Good Day 😊 UpVote?
['Breadth-First Search', 'Graph', 'Shortest Path', 'C++']