title: Bellman-Ford improvement: does it work?
body: <p><strong>I'am trying to improve the Bellman-Ford algorithm's performance and I would like to know if the improvement is correct.</strong></p>
  
  <p>I run the relaxing part not V-1 but V times, and I got a boolean variable involved, which is set <code>true</code> if any relax happened during the iteration of the outer loop. If no relax happened at the n. iteration where n &lt;= V, it returns from the loop with the shortest path, but if it relaxes at n = V iteration, that means we have a negative cycle. </p>
  
  <p>I thought it might improve runtime, since sometime we don't have to iterate for V-1 times to find the shortest path, and we can return earlier, and it's also more elegant than checking the cycle with another block of code.</p>
  
  <hr>
  
  <pre><code>AdjacencyListALD graph;
  
  int[] distTo;
  int[] edgeTo;
  
  public BellmanFord(AdjacencyListALD g)
  {
      graph = g;
  }
  
  public int findSP(int source, int dest)
  {
  
      // initialization
  
      distTo = new int[graph.SIZE];
      edgeTo = new int[graph.SIZE];
  
              for (int i = 0;i&lt;graph.SIZE;i++)
              {
                  distTo[i] = Integer.MAX_VALUE;
              }
  
              distTo[source] = 0;
  
      // relaxing V-1 times + 1 for checking negative cycle = V times
  
      for(int i = 0;i&lt;(graph.SIZE);i++)
      {
          boolean hasRelaxed=false;
  
          for(int j = 0;j&lt;graph.SIZE;j++)
          {
              for(int x=0;x&lt;graph.sources[j].length;x++)
              {
                  int s = j;
                  int d = graph.sources[j].get(x).label;
                  int w = graph.sources[j].get(x).weight;
  
                  if(distTo[d] &gt; distTo[s]+w)
                  {
                      distTo[d] = distTo[s]+w;
                      hasRelaxed = true;                      
                  }
              }
          }
          if(!hasRelaxed)
              return distTo[dest];
  
      }
      System.out.println("Negative cycle detected");
      return -1;
  
  
  }
  </code></pre>