3 APPROACHES || DIFFERENCE BETWEEN DIJKSTRA | BELMAN FORD |  FLOYDD WARSHELL || C++
DIJKSTRA ALGORITHM\n\n   HELPS TO FIND SSSP  ( SINGLE SOURCE SHORTEST PATH )  TO EVERY OTHER NODES\n   CAN BE IMPLEMENTED BY BOTH PRIORITY QUEUES AND SETS\n\nAD
**DIJKSTRA ALGORITHM**\n\n*   HELPS TO FIND SSSP  ( **SINGLE SOURCE SHORTEST PATH** )  TO EVERY OTHER NODES\n*   CAN BE IMPLEMENTED BY BOTH PRIORITY QUEUES AND SETS\n\n*ADVANTAGES*\n1.   T.C - O( ElogV )\n\n*DISADVANTAGES*\n1. IT WON\'T WORKS  FOR THE NEGATIVE EDGES\n2. UNABLE TO IDENTIFY NEGATIVE CYCLES\n```\nclass Solution\n{\npublic:\n  int networkDelayTime(vector<vector<int>> &times, int n, int k)\n  {\n    vector<pair<int, int>> adj[n + 1];\n    vector<int> dis(n + 1, 1e4);\n    dis[k] = 0;\n    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n    for (auto it : times)\n      adj[it[0]].push_back({it[1], it[2]});\n    pq.push({0, k});\n    int ans = 0;\n    while (!pq.empty())\n    {\n      auto it = pq.top();\n      pq.pop();\n      int distance = it.first;\n      int node = it.second;\n      for (auto i : adj[node])\n      {\n        if (distance + i.second < dis[i.first])\n        {\n          dis[i.first] = distance + i.second;\n          pq.push({distance + i.second, i.first});\n        }\n      }\n    }\n    for (int i = 1; i <= n; i++)\n    {\n      if (dis[i] == 1e4)\n        return -1;\n      ans = max(ans, dis[i]);\n    }\n    return ans;\n  }\n};\n```\n\n\n**BELMAN FORD ALGORITHM**\n\n* SIMLIAR TO DIJKSTRA\n* HELPS TO FIND SSSP( **SINGLE SOURCE SHORTEST PATH** ) TO EVERY OTHER NODES\n\n*INTUITION*\n*    JUST RELAX ALL THE EDGES N-1 TIMES SIMPLE !\n*   REALAXATION IS IF THE NEW DISTANCE IS SMALLER THAN PREVIOUS ONE JUST UPDATE IT OR (   *if( dist[u] + weight < dist[v] )  THAN  JUST UPDATE  --> dist[v] = dist[u] + weight* !\n\n*ADVANTAGES*\n1.  WORKS FOR NEGATIVE EDGES\n2.  ALSO HELPS US TO IDENTIFY NEGATIVE CYCLE !\n3.  SIMILIAR TO DIJKSTRA\n  \n **HOW TO IDENTIFY -VE CYLCES ???**   ---->   IF IT IS STILL RELAXING  IN THE Nth ITERATION THAN DEFINITELY IT WILL CONSIST A NEGATIVE CYCLE\n \n *DISADVANTAGES*\n1.   T.C - O ( V*E )\n\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n//         BELMAN FORD ALGORITHM\n        vector<int>dist(n+1,1e8);\n        dist[k]=0;\n        for(int i=0;i<n;i++)\n        {\n            for(auto &it:times)\n            {\n                int u=it[0];\n                int v=it[1];\n                int wt=it[2];\n                if(dist[u]!=1e8 && dist[u]+wt<dist[v])\n                {\n                    dist[v]=dist[u]+wt;\n                }\n            }\n        }\n        // for the -ve cycle if there is a -ve cycle the distance matrix will definitely reduce\n         for(auto &it:times)\n            {\n                int u=it[0];\n                int v=it[1];\n                int wt=it[2];\n                if(dist[u]!=1e8 && dist[u]+wt<dist[v])\n                {\n                   return -1;\n                }\n            }\n        //  if no -ve cycles\n        int ans=INT_MIN;\n        for(int i=1;i<=n;i++)\n        {\n            if(dist[i]==1e4) return -1;\n            ans=max(ans,dist[i]);\n        }\n        return ans==1e8?-1:ans;\n    }\n};\n```\n\n\n**FLOYD WARSHELL ALGORITHM**\n\n* HELPS TO FIND THE MSSP (**MULTI SOURCE SHORTEST PATH**)\n* USES ADJAENCY MATRIX NOT ADJEANCY LIST LIKE DIJKSTRA  AND BELMAN FORD\n* IT\'S A NORMAL BRUTE FORCE\n\n*ADVANTAGES*\n1.  HELPS TO FIND MSSP WHERE AS DUJKSTRA AND BELMAN FORD DON\'T GIVES U THIS LUXURY !\n2.  DETECTS -VE CYCLE\n3.  WORKS -VE EDGES TOO !\n\nDISADVANTAGES\n1. T.C- O( N^3 )\n\n```\nclass Solution\n{\npublic:\n  int networkDelayTime(vector<vector<int>> &times, int n, int k)\n  {\n    //         FLOYDD WARSHELL ALGORITHM\n    vector<vector<int>> adjaencyMatrix(n + 1, vector<int>(n + 1, 1e9));\n    for (auto it : times)\n    {\n      int src = it[0];\n      int dst = it[1];\n      int wt = it[2];\n      adjaencyMatrix[src][dst] = wt;\n    }\n    // created adjaency matrix finally !\n    for (int i = 0; i < n + 1; i++)\n    {\n      for (int j = 0; j < n + 1; j++)\n      {\n        if (j == 0)\n          adjaencyMatrix[i][j] = 0;\n        if (i == j)\n          adjaencyMatrix[i][j] = 0;\n      }\n    }\n    for (int via = 0; via < n + 1; via++)\n    {\n      for (int i = 0; i < n + 1; i++)\n      {\n        for (int j = 0; j < n + 1; j++)\n        {\n          adjaencyMatrix[i][j] = min(adjaencyMatrix[i][j], adjaencyMatrix[i][via] + adjaencyMatrix[via][j]);\n        }\n      }\n    }\n\n    int ans = -1;\n    for (auto it : adjaencyMatrix[k])\n    {\n      if (it == 1e9)\n        return -1;\n      if (it != 0)\n        ans = max(it, ans);\n    }\n    return ans;\n  }\n};\n```\n\n**UPVOTE IF THIS WAS HELPFUL !**\n\n\n
['Graph', 'C']