Dijsktra's Algorithm | Shortest Path in Undirected graph | C++ Solution
Intuition\nFind shortest path of each house to every other house\n\n# Approach\nFind shortest path of each house to every other house, and store it. Then just l
# Intuition\nFind shortest path of each house to every other house\n\n# Approach\nFind shortest path of each house to every other house, and store it. Then just loop through k, and the shortest dist of each house, and count the no. of times d == k\n\n# Complexity\n- Time complexity: O(N * N)\n\n- Space complexity: O(N * N)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> countOfPairs(int n, int x, int y) {\n        vector<int> adj[n + 1];\n        for(int i = 1; i <= n - 1; i++) {\n            adj[i].push_back(i + 1);\n            adj[i + 1].push_back(i);\n        }\n        if(x != y) {\n            adj[x].push_back(y);\n            adj[y].push_back(x);\n        }\n        \n        vector<vector<int>> store;\n        for(int h = 1; h <= n; h++) {\n            vector<int> dist(n + 1, 1e9);\n            dist[h] = 0;\n            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n            pq.push({0, h});\n            while(!pq.empty()) {\n                int d = pq.top().first;\n                int u = pq.top().second;\n                pq.pop();\n\n                for(auto v : adj[u]) {\n                    if(1 + d < dist[v]) {\n                        dist[v] = 1 + d;\n                        pq.push({1 + d, v});\n                    }\n                }\n            }\n            \n            store.push_back(dist);\n        }\n        \n        vector<int> ans;\n        for(int k = 1; k <= n; k++) {\n            int c = 0;\n            for(auto v : store) {\n                for(auto x : v) {\n                    if(x == k) c++;\n                }\n            }\n            ans.push_back(c);\n        }\n        \n        return ans;\n    }\n};\n```
['Graph', 'Shortest Path', 'C++']