Bellman ford optimisation

See more:

algorithm

C++14

Hello guys below is the implementation of bellman ford algorithm as we know that in v-1(at max) for loop(for(int i = 1; i <= V - 1; i++)) all edges will be relaxed completely but when it comes to detect negative weight cycle as i have mentioned below , the loop is running E times

i think there is no need to run that E times because if in the first iteration we found that distance is still minimising we can say that negative edge cycle is present,and if distance did not change in first iteration then it will not change for rest E-1 iteration Please correct me if i am wrong And even we can also optimise the number of time relaxation occurs,if we get the same minimum distance in any iteration we can exit the loop

What I have tried:

// The main function that finds shortest distances from src to
   // all other vertices using Bellman-Ford algorithm.  The function
   // also detects negative weight cycle
   void BellmanFord(struct Graph* graph, int src)
   {
       int V = graph->V;
       int E = graph->E;
       int dist[V];

       // Step 1: Initialize distances from src to all other vertices
       // as INFINITE
       for (int i = 0; i < V; i++)
           dist[i] = INT_MAX;
       dist[src] = 0;

       // Step 2: Relax all edges |V| - 1 times. A simple shortest
       // path from src to any other vertex can have at-most |V| - 1
       // edges
       for (int i = 1; i <= V - 1; i++)
       {
           for (int j = 0; j < E; j++)
           {
               int u = graph->edge[j].src;
               int v = graph->edge[j].dest;
               int weight = graph->edge[j].weight;
               if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                   dist[v] = dist[u] + weight;
           }
       }

       // Step 3: check for negative-weight cycles.  The above step
       // guarantees shortest distances if graph doesn't contain
       // negative weight cycle.  If we get a shorter path, then there
       // is a cycle.
       for (int i = 0; i < E; i++)
       {
           int u = graph->edge[i].src;
           int v = graph->edge[i].dest;
           int weight = graph->edge[i].weight;
           if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
               printf("Graph contains negative weight cycle");
       }

       printArr(dist, V);

       return;
   }