Ajuda com Implementação do Algoritmo de Floyd

System.out.println("Digite a cidade de Origem");
			String  cidadex, cidadey;
			Scanner cidade1 = new Scanner(System.in);
			cidadex= cidade1.nextLine();
			System.out.println("Digite a cidade de Destino");
			Scanner cidade2 = new Scanner(System.in);
			cidadey= cidade2.nextLine();
	        
			g.floyd(cidadex, cidadey);

public class Grafo {
    private int elementos;
    private Vertice[] vertices;
    private int[][] adj; 

   public Grafo(int v) {
       	elementos = 0;
        vertices = new Vertice[v];
        adj = new int[v][v];  
        
    }
//Inicio do Floyd 
public int floyd(String a, String b){
    // Inicialização
    int dist[i][j] = adj[i][j];                              //VAR Inteiro[1..n,1..n] dist := grafo
    int [][] pred = new int [this.elementos][this.elementos]; // VAR Inteiro[1..n,1..n] pred

   for(i=0;i<elementos;i++){
      for(i=0;i<elementos;i++){
           if(dist[i][j] < 99999999) {
                pred[i][j] = i;
        }
     }
   }
   // Laço principal do algoritmo
    for(int k=0;k<elementos;k++){
        for(i=0;i<elementos;i++){
            for(j=0;j<elementos;j++){
               if (dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pred[i][j] = pred[k][j];
    return dist; // não sei o que fazer com esta linha esta dando erro
            }
        }
     }
}

public int [][] floyd(String a, String b){

String  cidadex, cidadey;
Scanner leitor = new Scanner (System.in);
System.out.println("Digite a cidade de Origem");  
cidadex= leitor.nextLine();
# System.out.println("Digite a cidade de Destino");  
# cidadey=leitor.nextLine();

Grafo g1 = new Grafo(5); // suponha 5 vertices
int m1 [][]=new int[5][5];
m1 = g1.floyd(cidadex,cidadey); // m1 recebe o retorno do método floyd
for(int l=0;l<5;l++){
   for(int c=0;c<5;c++){   // lê os valores da matriz
      System.out.print(m1[ l ][ c ]+" "); 
   }
   System.out.println();
}

public int [][] floyd2 (String a, String b){
		//ROTINA fw(Inteiro[1..n,1..n] grafo)
		int i,k,j;
		
		int dist [][] = new int[this.elementos][this.elementos];
		int [][]pred = new int[this.elementos][this.elementos];
		int aux [][] = new int[this.elementos][this.elementos];
	   // VAR Inteiro[1..n,1..n] pred;
	    for(i=0;i<this.elementos;i++){ 
	        for(j=0;j<this.elementos;j++){
	        	dist[i][j] = this.adj[i][j];
	        	if (dist[i][j] < Integer.MAX_VALUE) {
	                pred[i][j] = i;
	        	}
	        }
	    }
	    //Laço principal do aloritmo
	    for(k=0;k<this.elementos;k++){
	        for(i=0;i<this.elementos;i++){ 
	        	for(j= 0;j<this.elementos;j++){ 
	                if( dist[i][j] > dist[i][k] + dist[k][j]){ 
	                	dist[i][j] = dist[i][k] + dist[k][j];
	                    pred[i][j] = pred[k][j];
	                    aux[k][j]=pred[i][j]+dist[i][j];
	                    //String arrayString = Arrays.deepToString( dist );
	            	    //System.out.println( Arrays.deepToString( dist ) );
	                    return pred;
	                    //return dist.toString();//dist;
	                }
	   
	                }
	        	}
	    	}
	System.out.println("1");
	return pred;
	      }

case 4:
			String  cidadex, cidadey;
			System.out.println("Digite a cidade de Origem");
			Scanner leitor = new Scanner(System.in);
			cidadex= leitor.nextLine();
			System.out.println("Digite a cidade de Destino");
			cidadey= leitor.nextLine();
			m1 = g.floyd2(cidadex,cidadey); // m1 recebe o retorno do método floyd  
			for(int l=0;l<17;l++){  
			    for(int c=0;c<17;c++){   // lê os valores da matriz  
			       System.out.print(m1[ l ][ c ]+" ");
			    }  
			    System.out.println("");  
			}

// Now the shortest distance between i and j will be in dist[i][j]
int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
 
   for ( k = 0; k < N; k++ )
      for ( i = 0; i < N; i++ )
         for ( j = 0; j < N; j++ )
            dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//FW is short for Floyd-Warshall
public class FW_sample {

	Node[] node;	// nodes
	int n;			// number of nodes
	Queue queue;	// the queue

	int nc;			// number of customers
	int[] customer;	// customers
	int[][] dist;	// distance between any pair of nodes
	
	// construct the FW with input arc file and customer file
	public FW_sample(String arcfile, String customerfile){
		this.readArc(arcfile);
		this.ReadCustomer(customerfile);
	}
	
	
	// this method reads the information of the nodes and arcs
	public void readArc(String filename){
		try{
			
			File input = new File(filename);
			BufferedReader br = 
				new BufferedReader(
						new InputStreamReader(
								new FileInputStream(input)));
			
			String line;
			String token;
			line = br.readLine();	// read the first line of the input file

			//parse the first line of the input file
			StringTokenizer st = new StringTokenizer(line);	
			token = st.nextToken();
			
			this.n = Integer.parseInt(token); // get the number of the nodes, n
			this.node = new Node[n]; // create n Nodes
			for(int i=0; i<n; i++){
				node[i] = new Node();
				node[i].num = i;
			}
			
			while((line = br.readLine())!= null){//read each rest lines in the file which contains arc information
				int from;
				int to;
				int cost;
				
				st = new StringTokenizer(line);
				token = st.nextToken();
				from = Integer.parseInt(token);
				token = st.nextToken();
				to = Integer.parseInt(token);
				token = st.nextToken();
				cost = Integer.parseInt(token);
				
				Arc arc = new Arc();
				arc.from_node = node[from];
				arc.to_node = node[to];
				arc.cost = cost;
				
				// if the node contains no arcs, this is the first out arc
				if (node[from].first_out_arc == null){
					node[from].first_out_arc = arc;
					node[from].last_out_arc = arc;
				}
				// else we should find the last arc 
				else{
					(node[from].last_out_arc).next_out_arc = arc;
					node[from].last_out_arc = arc;
				}
			}

			br.close();

		} catch (Exception e) {
			e.printStackTrace();
		}

	
	}

	// read the customers
	public void ReadCustomer(String filename){
		try{
			File customerFile = new File(filename);
			BufferedReader br = new BufferedReader(
									new InputStreamReader(
										new FileInputStream(customerFile)));
			
			String temp = br.readLine();
			this.nc = Integer.parseInt(temp);
			this.customer = new int[nc];

			// this may generate exceptions if the input file is in wrong format
			for(int i=0; i><nc; i++){
				temp = br.readLine();
				customer[i] = Integer.parseInt(temp);
			}
			
		}catch(Exception e){
			e.printStackTrace();
		}
	}

	// print the distance between each pair of customers
	public void printDist(){
		for(int i=0; i><nc; i++){
			for(int j=i; j><nc; j++){
				System.out.println(
						"The distance from customer " + i + "(node " + customer[i] + ")" +
						" to customer " + j + "(node " + customer[j] + ")" + 
						" is " + dist[customer[i]][customer[j]]);
			}
		}
	}
	
	
	// implement the Floyd-Warshall algorithm here:
	/* sample codes */
	public void floyd_Warshall(){
		this.dist = new int[n][n];
		
		for(int i=0; i><n; i++){
			for(int j=0; j><n; j++){
				if (i==j) dist[i][j] = 0;
				else dist[i][j] = 10000;
			}
		}

		for(int i=0; i><n; i++){
			Arc arc = node[i].first_out_arc;
			while(arc != null){
				dist[i][arc.to_node.num] = arc.cost;
				// here may change the graph to undirected
				//dist[arc.to_node.num][i] = arc.cost;
				arc = arc.next_out_arc;
			}
		}
		
		
		for(int k=0; k><n; k++){
			for(int i=0; i><n; i++){
				for(int j=0; j><n; j++){
					if (dist[i][j] > dist[i][k] + dist[k][j]){
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}
	}
	
	
	// this method finds the shortest path from node source to all nodes
	// by FIFO algorithm
	public void findPath(int source){
		for(int i=0; i<n; i++) node[i].dist = 10000;
		node[source].dist = 0;

		queue = new Queue();
		queue.addToTop(node[source]);
		
		while(!queue.isQueueEmpty()){
			
			Node t = queue.getAndRemoveTop();
			if (t==null) continue;//this should not happen if no error in the queue
			
			Arc arc = t.first_out_arc;
			while(arc!=null){
				int tmpdist = arc.to_node.dist;
				if (tmpdist > t.dist + arc.cost){
					arc.to_node.dist = t.dist + arc.cost;
					arc.to_node.pred = t;
					if (!queue.is_in_Q(arc.to_node)) queue.addToBottom(arc.to_node);
				}
				arc = arc.next_out_arc;
			}
		}
		
	}
	
	public static void main(String[] args) {
		FW_sample fw = new FW_sample("a1_data.txt", "customer.txt");
		fw.floyd_Warshall();
		fw.printDist();
		
		// the following codes print out the distance between all pairs of nodes 
		// by the FIFO algorithm, you may use this to check your result with 
		// Floyd-Warshall algorithm
		/*
		for(int i=0; i<fw.n; i++){
			fw.findPath(i);
			for(int j=0; j><fw.n; j++) 
				System.out.println(i+" to "+j+" : "+fw.node[j].dist);
			System.out.println("-------------");
		}
		*/
		
	}
}



class Node{				/* node structure */
	int num;			/* node id */ 
	Arc first_out_arc;	/* first outbound arc from the node */
	Arc last_out_arc;	/* last outbound arc from the node, you may or may not use this */
	Node pred;	// for shortest path
	Node next;	// for the queue
	int dist;

	public Node(){		// construciton
		this.num = -1;
		this.dist = -1;
		this.pred = null;
		this.first_out_arc = null;
		this.last_out_arc = null;
	}
}

class Arc{				/* arc structure */
	Node from_node;		/* from node of the arc	*/
	Node to_node;		/* to node of the arc */
	int cost;			/* some type of weight */
	Arc next_out_arc;	/* next arc on the list of outbound arcs of the same from node */

	public Arc(){
		this.from_node = null;
		this.to_node = null;
		this.cost = -1;
		this.next_out_arc = null;
	}
}

class Queue{
	Node top;		// top of the queue
	Node bottom;	// bottom of the queue
	int length;		//length of the queue
	
	public Queue(){
		this.top = null;
		this.bottom = null;
		length = 0;
	}

	// to check whether the queue is empty
	public boolean isQueueEmpty(){
		if (length==0) return true;
		else return false;
	}

	// to check whether a node is in the queue
	public boolean is_in_Q(Node node){
		if (node==null) return false;
		if (this.top == null || this.length == 0) return false;
		Node t = this.top;
		while(t != null){
			if (t == node) return true;
			t = t.next;
		}
		return false;
	}

	// add a node to the top of the queue
	public void addToTop(Node node){
		if (node == null) return;
		if (this.length == 0){
			this.top = node;
			this.bottom = node;
			this.length ++;
		}
		else{
			node.next = top;
			this.top = node;
			this.length ++;
		}
	}

	// add a node to the bottom of the queue
	public void addToBottom(Node node){
		if (node == null) return;
		if (this.length == 0){
			this.top = node;
			this.bottom = node;
			this.length ++;
		}
		else{//length>0
			this.bottom.next = node;
			this.bottom = node;
			node.next = null;
			this.length ++;
		}
	}
	
	// get the top of the queue, and remove it from the queue
	public Node getAndRemoveTop(){
		if (this.top == null || this.length == 0) return null;
		else {
			Node t = this.top;
			if (this.length > 1){
				this.top = this.top.next;
			}
			else{// length == 1
				this.top = null;
				this.bottom = null;
			}
			t.next = null;
			this.length --;
			return t;
		}
	}

	
}

/*
 * Shortest Path Between 2 given cities
 * using Floyd's Algorithm
 *
 *
 *
 *
 */
import java.io.*;
 

/**
 * GOOGLE
 * 
 */
public class Main{
   
 
    public Main() {
    }
   
    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        int S[][] = new int [6][6]; /* Creating the adjacency matrix, this is the last adjacency matrix */
               
                S[0][0] = 0;//Defining Values
                S[0][1] = 0;
                S[0][2] = 0;
                S[0][3] = 0;
                S[0][4] = 0;
                S[0][5] = 0;
               
                S[1][0] = 0;
                S[1][1] = 0;
                S[1][2] = 2;
                S[1][3] = 3;
                S[1][4] = 2;
                S[1][5] = 4;
               
                S[2][0] = 0;
                S[2][1] = 1;
                S[2][2] = 0;
                S[2][3] = 4;
                S[2][4] = 4;
                S[2][5] = 4;
               
                S[3][0] = 0;
                S[3][1] = 1;
                S[3][2] = 4;
                S[3][3] = 0;
                S[3][4] = 4;
                S[3][5] = 4;
               
                S[4][0] = 0;
                S[4][1] = 2;
                S[4][2] = 2;
                S[4][3] = 3;
                S[4][4] = 0;
                S[4][5] = 3;
               
                S[5][0] = 0;
                S[5][1] = 4;
                S[5][2] = 4;
                S[5][3] = 4;
                S[5][4] = 4;
                S[5][5] = 0;
               
     
               
        System.out.println("Escribe la ciudad de origen");/*Ask for the initial point, from 1 to 5 */
 

        int i = Integer.parseInt(in.readLine());
       
        System.out.println("Escribe la ciudad destino");/*Ask for the final point*/
        int j = Integer.parseInt(in.readLine());
       
        int l = j;
        int k=0;
        String ruta = "";
        String ruta0 = "";
       
        if (S[i][j] == j) /*If j = S[i][j] there is a direct conection between i and j */
            System.out.println("La ruta mas corta es ir de: " + i + " a " + j );
       
        else{ /* if theres no direct connection between i and j, S[][] has to be evaluated to find the shortest path. */
 
/*Here is the main problem... this how i programmed the last part of the *algorithm, but it is not
*correct.
*These Whiles has to check if S[i][l] is equal to l if so, there is a direct *connection between i
*and j, if not between i and j you have to pass through S[i][j], and *evaluate this point with
*the new value of l
*/
            k = S[i][l];
            while ( k != l){
                ruta = S[i][l] + "" + ruta + "";
                l = S[i][l];
               
            }
           
            k = S[l][j];
             while ( k != l){
                ruta0 = S[l][j] + "" + ruta0 + "";
                l = S[l][j];
               
            }
            if(j<i)
            System.out.println("La ruta mas corta a tomar es la sigueinte: " + i + " " + ruta +
 
" " + ruta0 + " "+ j);
            else
                System.out.println("La ruta mas corta a tomar es la sigueinte: " + i + " " +
 
ruta0 + " " + ruta + " "+ j);
         
 
           
        }
       
       
       
       
    }
   
}

// Floyd-Warshall algorithm
//


public class FloydWarshall {
  
  // Debugging for internal use.
  private static final boolean debug = false;
  
  int numVertices;                   // Number of vertices (when initialized).

  double[][] adjMatrix;              // The adjacency matrix (given as input).

  double[][] Dk, Dk_minus_one;       // Matrices used in dynamic programming.


  public void initialize (int numVertices)
  {
    this.numVertices = numVertices;

    // Initialize Dk matrices.
    Dk = new double [numVertices][];
    Dk_minus_one = new double [numVertices][];
    for (int i=0; i < numVertices; i++){
      Dk[i] = new double [numVertices];
      Dk_minus_one[i] = new double [numVertices];
    }
  }

  
  public void allPairsShortestPaths (double[][] adjMatrix)
  {
    // Dk_minus_one = weights when k = -1
    for (int i=0; i<numVertices; i++) {
      for (int j=0; j><numVertices; j++) {
        if (adjMatrix[i][j] > 0)
          Dk_minus_one[i][j] = adjMatrix[i][j];
        else 
          Dk_minus_one[i][j] = Double.MAX_VALUE;
        // NOTE: we have set the value to infinity and will exploit
        // this to avoid a comparison.
      }
    }
    
    // Now iterate over k.

    for (int k=0; k<numVertices; k++) {

      // Compute Dk[i][j], for each i,j

      for (int i=0; i><numVertices; i++) {
        for (int j=0; j><numVertices; j++) {
          if (i != j) {

            // D_k[i][j] = min ( D_k-1[i][j], D_k-1[i][k] + D_k-1[k][j].
            if (Dk_minus_one[i][j] >< Dk_minus_one[i][k] + Dk_minus_one[k][j])
              Dk[i][j] = Dk_minus_one[i][j];
            else 
              Dk[i][j] = Dk_minus_one[i][k] + Dk_minus_one[k][j];

          }
        }
      }

      // Now store current Dk into D_k-1
      for (int i=0; i<numVertices; i++) {
        for (int j=0; j><numVertices; j++) {
          Dk_minus_one[i][j] = Dk[i][j];
        }
      }

    } // end-outermost-for


    // Next, build the paths by doing this once for each source.

    // ... (not shown) ...
  }
  


  //---------------- Test case  -----------------------------------------------
    

  public static void main (String[] argv)
  {
    // A test case.
      double[][] adjMatrix = {
        {0, 1, 7, 0, 5, 0, 1},
        {1, 0, 1, 0, 0, 7, 0},
        {7, 1, 0, 1, 7, 0, 0},
        {0, 0, 1, 0, 1, 0, 0},
        {5, 0, 7, 1, 0, 1, 0},
        {0, 7, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 1, 0},
      };

      int n = adjMatrix.length;
      FloydWarshall fwAlg = new FloydWarshall ();
      fwAlg.initialize (n);
      fwAlg.allPairsShortestPaths (adjMatrix);
      
      // Print paths ... (not shown) ...

  }
  

}