[C++] Djikstra's Algorithm  || Bellman Ford || Concise and very easy to understand
Approach : Dijkstra\'s Shortest Path Algorithm (Using Priority queue)\n\nFirst, from the given input vector, we have to make the adjacency list for the required
***Approach : Dijkstra\'s Shortest Path Algorithm (Using Priority queue)***\n\nFirst, from the given input vector, we have to make the adjacency list for the required directed weighted graph for Dijkstra\'s Algorithm\n\nTo calculate the minimum distance to all other nodes from given "k" node. For minimum distance , we make a minimum heap using C++ STL priority queue.\n\n If our maximum distance is INT_MAX, that means we have not visited some nodes (hence distance vector was initialized with INT_MAX in starting). So we will return -1.\nElse we will return maximum distance.\n\n***Dijkstra (Time Complexity)- V + ElogV***\n\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n         vector<int>dis(n+1,INT_MAX);\n         priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;\n        \n        vector<vector<int>>adj[n+1];\n        \n        for(int j=0;j<times.size();j++)   // Graph creation\n            {\n                int u=times[j][0];\n                int v=times[j][1];\n                int w=times[j][2];\n                adj[u].push_back({v,w});\n          }\n         \n         dis[k]=0;                          // Time from K to K is 0\n         pq.push({0,k});\n        \n         while(!pq.empty())\n         {\n              int u=pq.top().second;\n              pq.pop();\n             \n             for(auto vec:adj[u])       // vec is vector containing v and w\n                {\n                    int v=vec[0];\n                    int w=vec[1];\n                 \n                   if(dis[u]+w<dis[v])\n                      {\n                        pq.push({dis[u]+w,v});\n                        dis[v]=w+dis[u];\n                      }\n                }\n          }\n\t   \n        int ans=0;\n        for(int i=1;i<=n;i++)\n            {\n              if(dis[i]==INT_MAX) return -1;\n              ans=max(ans,dis[i]);\n          }\n        return ans;\n     }\n};\n```\nWe can further optimize this last loop, by keeping the count of nodes which are processed and also we can store answer in another variable in while loop too.\n```\n        int ans=0;\n        for(int i=1;i<=n;i++)\n            {\n               if(dis[i]==INT_MAX) return -1;\n               ans=max(ans,dis[i]);\n           }\n         return ans;\n```\n\n----------------------------------------------------------------------------------------\n----------------------------------------------------------------------------------------\n----------------------------------------------------------------------------------------\n----------------------------------------------------------------------------------------\n\n\n***2nd Approach Using [ Bellman Ford ]***\n\n***Bellman Ford(Time Complexity) - VE***\n\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        \n        \n        vector<int>dis(n+1,INT_MAX);\n        dis[k]=0;\n        for(int i=1;i<n;i++)\n           {\n             for(int j=0;j<times.size();j++)\n                 {\n                   int u=times[j][0];\n                   int v=times[j][1];\n                   int w=times[j][2];\n                 \n                   if(dis[u]!=INT_MAX && dis[u]+w<dis[v])\n                   {\n                     dis[v]=w+dis[u];\n                   }\n                }\n           }\n\t\t   \n        int ans=0;\n        for(int i=1;i<=n;i++)\n           {\n            if(dis[i]==INT_MAX) return -1;    // If any node is not reachable from k\n            ans=max(ans,dis[i]);\n           }\n        return ans;\n        \n    }\n};\n```\n
['Graph', 'C', 'C++']