C++ || Dijkstra✅ + Bellman Ford✅ + (Some idea on Floyd-Warshall)✅ || Easy💡 and Fast🔥
Here question asks to return minimum time it takes for all the n nodes to receive the signal. Which means it wants to say that find the shortest time to reach a
Here question asks to return minimum time it takes for all the n nodes to receive the signal. Which means it wants to say that find the shortest time to reach all the nodes and then return maximum time out of it.\n\nBasically there is some node which will take more time then other nodes. So have to minimize that time.\n\nMinimum time to reach all nodes = max({src to 1, src to 2, ..... , src to N})\n\n---\n\n# Dijkstra Algo\n- Time complexity: $$O(ElogV)$$\n- Space complexity: $$O(E+V)$$\n\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        vector<vector<pair<int, int>>> adj(n);  // Adj List\n        for(auto e: times){\n            // Storing vertices by subtracting 1 as nodes given as 1 to N.\n            int u = e[0]-1, v = e[1]-1, wt = e[2];  \n            adj[u].push_back({v, wt});\n        }\n\n        vector<int> dist(n, 1e9);   //Distance array\n\n        // Min Heap to arrange distance from low to high \n        // {Distance, Node}\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n\n        dist[k-1] = 0;  // Distance of src to src will be 0\n        pq.push({0, k-1});  // Push the current state of source node\n\n        while(!pq.empty()){\n            auto [nDist, node] = pq.top();  // Getting top node\n            pq.pop();\n            \n            // If dist of node has been updated to lower value then skip further calculation.            \n            if(nDist > dist[node])  continue;\n\n            // Traversing all adjacent nodes\n            for(auto [adjNode, edgeWt] : adj[node]){\n\n                //Usual bellman equation checking and pushing node\'s state\n                if(dist[adjNode] > nDist + edgeWt){\n                    dist[adjNode] = nDist + edgeWt;\n                    pq.push({dist[adjNode], adjNode});\n                }\n            }\n        }\n\n        // Getting maximum answer\n        int ans = 0;\n        for(int i = 0; i<n; i++){\n            // If any node\'s distance is still 1e9 (infinite) return -1\n            if(dist[i] == 1e9)  return -1;\n            ans = max(ans, dist[i]);\n        }\n\n        return ans;\n    }\n};\n```\n---\n\n\n# Bellman Ford Algo\n- Time complexity: $$O(EV)$$\n- Space complexity: $$O(V)$$\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        vector<int> dist(n+1, 1e9); //Distance array\n        dist[k] = 0;    // Distance of src to src is 0\n\n        // Relaxing all edges N-1 times\n        for(int i = 0; i<n-1; i++){\n            // Traversing all edges\n            for(auto e : times){\n                int u = e[0], v = e[1], wt = e[2];\n\n                // Relaxing only if distance of u is not infinite\n                if(dist[u] != 1e9)\n                    dist[v] = min(dist[v], dist[u] + wt);\n            }\n        }\n\n        // Getting maximum answer\n        int ans = 0;\n        for(int i = 1; i<=n; i++){\n            if(dist[i] == 1e9)  return -1;\n            ans = max(ans, dist[i]);\n        }\n\n        return ans;\n    }\n};\n```\n\n---\n\n# Floyd Warshall Algo\n- Time complexity: $$O(V^3)$$\n- Space complexity: $$O(V^2)$$\n\n\nThis algo is Multi-Source shortest path algorithm and is the costliest shortest path algorithm.\nIt works well when we have find the shortest of each pair of nodes or graph has negative weights cycle. But here we have to find distance from single source only and here don\'t have any negative weight cycles.\nIf you want to try that algo it can applied to this question easily without any changes to algo.\n\n---\n\n```\nThank you\nIf you learn/found something new, please Upvote \uD83D\uDC4D\n```\n---\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
['Breadth-First Search', 'Heap (Priority Queue)', 'Shortest Path', 'C++']