Efficient Shortest Path Computation and Path Counting using Dijkstra's Algorithm
Intuition\nWe use Dijkstra\'s algorithm to find the shortest paths from a given source node to all other nodes in a weighted undirected graph.\n\n# Approach\n1.
# Intuition\nWe use Dijkstra\'s algorithm to find the shortest paths from a given source node to all other nodes in a weighted undirected graph.\n\n# Approach\n1. Graph Representation: The graph is represented using an adjacency list, which is a collection of lists (in this case, implemented using an unordered map) where each list contains the neighbors of a particular node along with the corresponding edge weights.\n\n2. Dijkstra\'s Algorithm: Dijkstra\'s algorithm is employed to find the shortest paths from a given source node to all other nodes in the graph. The algorithm maintains two main data structures:\n\n1->   Distance Vector (dist): This vector stores the shortest distances from the source node to all other nodes. Initially, all distances are set to a maximum value (LLONG_MAX), indicating infinity.\n2->   Path Count Vector (pathCount): This vector keeps track of the number of shortest paths from the source node to each node in the graph.\n\n3. Priority Queue (Set): A set (st) is used as a priority queue to efficiently retrieve the node with the smallest tentative distance during each iteration of the algorithm. The set is ordered based on the tentative distances of the nodes.\n\n4. Main Loop: The main loop of the algorithm continues until there are no more nodes to explore in the set. During each iteration:\n1-->  The node with the smallest tentative distance is extracted from the set.\n2-->  Its neighbors are traversed, and if a shorter path is found to any neighbor, the distance and path count for that neighbor are updated accordingly.\n3-->  If the distance to a neighbor is the same as the current shortest distance, the path count for that neighbor is incremented by the path count of the current node.\n\n5. Counting Paths: Once Dijkstra\'s algorithm completes execution, the countPaths function returns the path count for the destination node, which represents the number of shortest paths from the source node to the destination node.\n\n6. Modular Arithmetic: Modular arithmetic is employed to handle large numbers and prevent integer overflow. The path count is computed modulo M=1e9+7 to ensure that the result remains within the bounds of an integer.\n\nOverall, the approach efficiently finds the shortest paths and counts the number of such paths from the source node to the destination node using Dijkstra\'s algorithm and appropriate data structures.\n\n# Complexity\n- Time complexity:\nO((V + E) log V + n)\n\n- Space complexity:\nO(V + E)\n\n# Code\n```\nclass Solution {\npublic:\n    const int M=1e9+7;\n    vector<long long> dijkstra(vector<vector<int>> &roads, int n, int source, vector<int>& pathCount) {\n        //adj list\n        unordered_map<int,list<pair<int,int>>>adj;\n        for(int i=0;i<roads.size();i++) \n        {\n            int u=roads[i][0];\n            int v=roads[i][1];\n            int w=roads[i][2]; //weights\n            adj[u].push_back(make_pair(v,w));\n            adj[v].push_back(make_pair(u,w));\n        }\n\n        vector<long long>dist(n,LLONG_MAX);\n        pathCount.resize(n, 0); \n\n        set<pair<long long,int>>st;\n        dist[source]=0;\n        pathCount[source]=1;\n        st.insert(make_pair(0, source));\n\n        while(!st.empty())\n        {\n            //fetch the top record\n            auto top= *(st.begin());\n            long long nodeDist=top.first;\n            int node=top.second;\n\n            //remove top now\n            st.erase(st.begin());\n\n            //ttraverse neighbors\n            for(auto j:adj[node])\n            {\n                int  neighbor=j.first;\n                int  weight=j.second;\n                if(nodeDist+weight<dist[neighbor])\n                {\n                    auto record=st.find(make_pair(dist[neighbor], neighbor));\n                    //if record found then erase it\n                    if(record!=st.end()) \n                    {\n                        st.erase(record);\n                    }\n                    //updatee in dist vector\n                    dist[neighbor]=nodeDist+weight;\n                    pathCount[neighbor]=pathCount[node]; \n\n                    // push record in set\n                    st.insert(make_pair(dist[neighbor],neighbor));\n                } \n                else if(nodeDist+weight==dist[neighbor]) \n                {\n                    //pathCount[neighbor]+=pathCount[node];\n                    pathCount[neighbor]=(pathCount[neighbor]+pathCount[node])%M;\n                }\n            }\n        }\n        return dist;\n    }\n\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<int>pathCount;\n        vector<long long>dist =dijkstra(roads, n, 0, pathCount);\n        \n        //sinve last node is destination\n        return pathCount[n-1];\n    }\n};\n\n```
['Graph', 'Shortest Path', 'C++']