Bellman ford algorithm

 shortest path in direct graph. 

Given a graph and a source vertex src in the graph, find the shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges. But time complexity of Bellman-Ford is O(V * E), which is more than Dijkstra. 

Distance from the Source (Bellman-Ford Algorithm): 

class Solution {

  public:

    /*  Function to implement Bellman Ford

    *   edges: vector of vectors which represents the graph

    *   S: source vertex to start traversing graph with

    *   V: number of vertices

    */

    vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {

        // Code here

        vector<int>dis(V , 1e8);

        dis[S] = 0;

        for(int i =0 ; i < V-1 ; i++)

        {

            for(auto x : edges)

            {

                int u = x[0];

                int v = x[1];

                int wt = x[2];

                if(dis[u] + wt < dis[v])

                {

                    dis[v] = dis[u] + wt;

                }

            }

            

        }

        vector<int>dist1 = dis;

        for(auto x : edges)

            {

                int u = x[0];

                int v = x[1];

                int wt = x[2];

                if(dis[u] + wt < dis[v])

                {

                    dis[v] = dis[u] + wt;

                }

            }

        for(int i =0 ; i < dis.size() ; i++)

        {

            if(dist1 != dis)

            {

                return {-1};

            }

        }

        return dis;

        

    }

};