title: Bellman Ford detecting negative cycle of shortest length
body: <p>Solving this Arbitage problem of UVA <a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=40" rel="nofollow">http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=40</a> but I am stuck with finding the negative cycle of shortest length(length here is number of vertices).Here is my code that successfully detects the negative cycle</p>
  
  <pre><code>import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  
  public class _104 {
  
  public static void main(String[] args) throws NumberFormatException,
          IOException {
      BufferedReader reader = new BufferedReader(new InputStreamReader(
              System.in));
      String input;
      while ((input = reader.readLine()) != null) {
          int n = Integer.parseInt(input);
          double[][] cost = new double[n + 1][n + 1];
          double[] spEstimate = new double[n + 1];
          int parent[] = new int[n + 1];
          for (int i = 0; i &lt; n + 1; i++) {
              spEstimate[i] = Double.MAX_VALUE;
              cost[0][i] = 0;
              cost[i][0] = Double.MAX_VALUE;
              parent[i] = Integer.MAX_VALUE;
          }
          spEstimate[0] = 0.0;
          parent[0] = 0;
          for (int i = 1; i &lt; n + 1; i++) {
              String[] line = reader.readLine().split("\\s+");
              for (int j = 1; j &lt; n + 1; j++) {
                  if (i == j) {
                      cost[i][j] = 0;
                  } else if (i &lt; j) {
                      cost[i][j] = -(Math
                              .log(Double.parseDouble(line[j - 2])) / Math
                              .log(2));
                  } else {
                      cost[i][j] = -(Math
                              .log(Double.parseDouble(line[j - 1])) / Math
                              .log(2));
                  }
              }
          }
          int save = 1, s = 1;
          boolean flag = BellmanFord(n, cost, spEstimate, parent);
           display(cost);
          // Relax all edges once more
          boolean brk = true;
          for (int i = 0; i &lt; cost.length &amp;&amp; brk; i++) {
              for (int j = 0; j &lt; cost.length &amp;&amp; brk; j++) {
                  //relax(i, j, spEstimate, cost[i][j], parent);
              }
          }
  
          ArrayList&lt;Integer&gt; path = new ArrayList&lt;Integer&gt;();
          while (parent[save] != s) {
              path.add(save);
              save = parent[save];
          }
          if (flag) {
              System.out.println("no arbitrage sequence exists");
          } else {
              path.add(0, path.get(path.size() - 1));
              for (int i = path.size() - 1; i &gt;= 0; --i) {
                  System.out.println(path.get(i));
              }
          }
      }
      reader.close();
  }
  
  public static boolean BellmanFord(int n, double[][] cost, double[] sp,
          int[] parent) {
      for (int k = 0; k &lt; n - 1; k++) {
          for (int i = 0; i &lt; cost.length; i++) {
              for (int j = 0; j &lt; cost.length; j++) {
                  relax(i, j, sp, cost[i][j], parent);
              }
          }
      }
      // Relax all edges once more to detect cycle
      for (int i = 0; i &lt; cost.length; i++) {
          for (int j = 0; j &lt; cost.length; j++) {
              if (sp[j] &gt; (sp[i] + cost[i][j])) {
                  return false;
              }
          }
      }
      return true;
  }
  
  static void relax(int i, int j, double[] sp, double cij, int[] parent) {
      if (sp[j] &gt; (sp[i] + cij)) {
          sp[j] = sp[i] + cij;
          System.out.println("relaxed " + i + " " + j + " " + cij + " "
           + sp[i] + " " + sp[j]);
          parent[j] = i;
      }
  }
  
  static void display(double[][] cost) {
      System.out.println("Display Cost");
      for (int i = 0; i &lt; cost.length; i++) {
          for (int j = 0; j &lt; cost.length; j++) {
              System.out.print(cost[i][j] + "\t");
          }
          System.out.println();
      }
  }
  
  static void display(double[] sp) {
      for (int i = 0; i &lt; sp.length; i++) {
          System.out.println(sp[i]);
      }
  }
  }
  </code></pre>