Simple modification in dijkstra's algorithm
Slight Modification in dijkstra\'s algorithm\n# Approach\n### 1. Initialization:\n- Mark the distance to the source node as 0 and to all other nodes as LONG_MAX
Slight Modification in dijkstra\'s algorithm\n# Approach\n### **1. Initialization:**\n- Mark the distance to the source node as 0 and to all other nodes as LONG_MAX.\n- Use a priority queue (min-heap) to efficiently fetch the next node with the smallest tentative distance.\n\n---\n\n\n### **2. Main Loop:**\n- Extract the node (u) with the smallest distance from the priority queue.\n- For each unvisited neighbor of this node (v), calculate the distance through the current node.\n- Two possiblities\n1. If the distance of a neighbour (dist[v]) is greater than the dist[u] + w, update the shortest distance of that neighbor (dist[v]) and update its entry in the priority queue. Also intialize count vector which is number of possible ways to reach the neighbour(v) from the parent (u), which is same as the (u).\n2. If the distance of a neighbour (dist[v]) is equal to the dist[u] + w, in this case we don\'t need to add entry in the pririty queue, we just need to update the count[v].\n\n- Mark the current node as visited so that it will not be processed again.\n\n---\n\n\n### **3. Termination:**\n- The algorithm terminates when the priority queue is empty or all reachable vertices have been visited.\n- Return number of ways to reach destination node with min distance which is **count[n-1]** in our case.\n\n\n---\n\n\n# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        unordered_map <int,vector <pair<int,int>>> adj;\n        // Create Adjacency List\n        for(auto &i: roads){\n            adj[i[0]].push_back({i[1],i[2]});\n            adj[i[1]].push_back({i[0],i[2]});\n\n        }\n\n        // Priority queue to efficiently fetch the next node with the smallest tentative distance\n        priority_queue <pair<long,int>, vector <pair<long,int>>, greater<pair<long,int>>> q;\n        // To store the minimum distance to reach from source (here 0) to the particular node \n        vector <long> dist(n,LONG_MAX);\n        // To store which node is visited\n        vector <bool> vis(n,false);\n        // To store number of possible paths with minimum distance \n        vector <int> count(n,0);\n\n        // Start with the source node 0\n        q.push({0,0});\n                \n        dist[0] = 0;\n        count[0] = 1;\n        int mod = 1e9+7;\n        while(!q.empty()) {\n            auto curr = q.top();\n            q.pop();\n            int u = curr.second;\n            if(vis[u])\n                continue;\n            vis[u] = true;\n            for(auto &next:adj[u]) {\n                int v = next.first; \n                int w = next.second;\n                if(!vis[v]){\n                    if(dist[v]>dist[u]+w){\n                        dist[v] = dist[u]+w;\n                        q.push({dist[v],v});\n                        count[v] = count[u]%mod;\n                    }\n                    else if(dist[v]==dist[u]+w) {\n                        count[v] = (count[v] + count[u])%mod;\n                    }\n                }\n                       \n            }\n\n        }\n        \n        return count[n-1];\n    }\n};\n```\nFeel free to comment down your queries, Thanks !
['Dynamic Programming', 'C++']