Algorithm - Bellman-Ford

BellmanFord.java

import java.util.Scanner;

/**
 * Bellman-Ford Java Implementation
 */
public class BellmanFord {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    while (true) {
      int n = sc.nextInt();
      int m = sc.nextInt();

      if (n == 0 && m == 0) {
        return;
      }

      float[][] D = new float[n][n];
      for (int i = 0; i < m; i++) {

        int x = sc.nextInt();
        int y = sc.nextInt();
        float f = sc.nextFloat();

        D[x][y] = f;
        D[y][x] = f;
      }

      float[] dist = new float[n];
      dist[0] = 0;
      for (int i = 1; i < n; i++) {
        dist[i] = -1;
      }

      for (int repeats = 0; repeats < n; repeats++) {
        boolean updated = false;
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
            if (D[i][j] > 0) {
              float candidate = dist[i] + D[i][j];
              if (candidate < dist[j]) {
                dist[j] = candidate;
                updated = true;
              }
            }
          }
        }

        if (!updated) {
          break;
        }
      }

      System.out.printf("%.4f\n", dist[n - 1]);
    }
  }

}