All Three Approaches | Easy Solution | Commented Explanation |
Upvote if you like it and finds helpful !\n\nApproach 1 : DFS\n\n  Time complexity: O((N - 1)! + ElogE\n Space complexity: O(N + E)O(N+E)\n\n\n\nclass Solution 
***Upvote if you like it and finds helpful !***\n\n**Approach 1 : DFS**\n\n  ***Time complexity: O((N - 1)! + ElogE***\n ***Space complexity: O(N + E)O(N+E)***\n\n\n```\nclass Solution {\npublic:\n     static bool sortbysec ( const pair<int,int>&a , const pair<int,int>&b )\n    {\n        return a.second < b.second ;\n    }\n    \n    void dfsutil(int src , vector<vector<pair<int,int>>>& adj, vector<bool>& visited ,vector <int>& receiving_time , int t )\n    {\n         receiving_time[src] = t;  \n         visited[src] = true;\n         for(int i = 0 ; i < adj[src].size(); i++)\n         {\n             int neigbhour = adj[src][i].first;\n             int time = adj[src][i].second;\n             \n             if(!visited[neigbhour])\n            {\n                 dfsutil(neigbhour , adj ,visited , receiving_time , t+time);\n            }\n             else if( visited[neigbhour] && receiving_time[neigbhour] > t+time)\n             {\n                 dfsutil(neigbhour , adj, visited , receiving_time , t+time);\n             }\n         }\n    }\n     \n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n     vector<vector<pair<int,int>>> adj(n+1);  \n     vector<bool>visited(n+1,false); visited[0] = true;\n     vector<int>timestramp(n+1,INT_MAX); timestramp[0] = 0;\n        \n     for(auto &time : times )     // creating adj list by adding edges from source to destination node.\n     {\n         adj[time[0]].push_back({time[1],time[2]});\n     }\n        \n     for(int i =0 ; i< n+1 ; i++) // Sort pair according to timestramp in ascending order.\n     {\n         sort(adj[i].begin(), adj[i].end() , sortbysec);   \n     }\n     \n     dfsutil(k , adj ,visited ,timestramp , 0); \n    \n     for(int i = 1 ; i < visited.size(); i++)\n         if(!visited[i]) return -1;\n     \n     return *max_element(timestramp.begin(), timestramp.end());\n    }\n};\n```\n\n##### Approach 2 :  Bellman Ford Solution \n\n**Time complexity: O(NE)\nSpace complexity: O(N)**\n\n```\nint bellmanFord(vector<vector<int>>& times, int n, int k) {\n        // delay[i] = time to reach kth node\n        vector<int> delay(n+1, INT_MAX);\n        // we start from  node kth node as source, all other nodes are destinations\n        delay[k] = 0;\n        \n        for(int i = 0; i < n; i++) {\n            for(auto edge: times) {\n                // delay[dst] > delay[src] + wt\n                delay[edge[1]] = min(delay[edge[1]], \n                                     delay[edge[0]] == INT_MAX ? INT_MAX : delay[edge[0]] + edge[2]);\n            }\n        }\n        // 0th element is dummy, so skip . Find the max delay time, this will decide the overall delay\n        int max_delay = *max_element(delay.begin() + 1, delay.end());\n        \n        return max_delay == INT_MAX ? -1 : max_delay;\n    }\n\t   int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        return bellmanFord(times, n, k);\n    }\n```\n\n\n#####  Optimised Solution\n##### Approach 3 : Djikstra Using DFS Solution \n\n##### Time complexity:  O(V+E)\n##### Space complexity: O(N)\n\n```\nclass Solution {\npublic:\nint networkDelayTime(vector<vector>& times, int n, int k) {\n\n    vector<vector<pair<int, int>>> graph(n + 1);\n    for(auto &i : times)\n        graph[i[0]].push_back({i[1], i[2]});\n    \n    vector<int> d(n + 1, INT_MAX);\n    vector<bool> visited(n + 1, false);\n    d[k] = 0;\n    dfs(graph, k, d, 0, visited);\n    \n    for(int i = 1; i <= n; i++)\n        if(!visited[i])\n            return -1;\n            \n    int ans = 0;\n    for(int i = 1; i <= n; i++)\n        ans = max(ans, d[i]);\n    \n    return ans;\n}\n\nvoid dfs(vector<vector<pair<int, int>>> &graph, int i, vector<int> &d, int tmp, vector<bool> &visited)\n{\n    visited[i] = true;\n    for(auto &j : graph[i])\n        if(tmp + j.second < d[j.first])\n            d[j.first] = tmp + j.second, dfs(graph, j.first, d, d[j.first], visited);\n}\n};\n```\n\n######  Comment down if You have any doubt !
['Depth-First Search', 'C']