Оптимизации Беллмана Форда

---

Привет, ребята ниже приведена реализация алгоритма Беллмана Форда , так как мы знаем, что в v-1(at max) for loop(for(int i = 1; i <= V - 1; i++)) все ребра будут полностью расслаблены, но когда дело доходит до обнаружения отрицательного весового цикла, как я уже упоминал ниже, цикл выполняется E раз

я думаю,что нет необходимости запускать это E раз,потому что если в первой итерации мы обнаружили, что расстояние все еще минимизируется, мы можем сказать, что отрицательный реберный цикл присутствует, и если расстояние не изменилось в первой итерации, то оно не изменится для остальных E-1 итераций, пожалуйста, поправьте меня, если я ошибаюсь, и даже мы можем также оптимизировать количество времени релаксации, если мы получим то же самое минимальное расстояние в любой итерации, мы можем выйти из цикла

Что я уже пробовал:

// 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;
   }

---