floyd.java

Easy implementation of PRIM and DIJKSTRA algorims for graph sorting. It also permit comparison of ti

import java.io.FileOutputStream;

public class Floyd {
	class FloydResult {
		int D[][];
		int P[][];
		public FloydResult(Grafo G) {
			D = new int[G.NumVertices][G.NumVertices];
			P = new int[G.NumVertices][G.NumVertices];
		}
		
  	void SaveToFile(String File) {
  		try {
  			FileOutputStream oe = new FileOutputStream(File);
        for(int o = 0; o < D.length; o++) {
    			oe.write(new String("Nodo Origen:\t" + o + "\r\n").getBytes());
    			oe.write(new String("Caminos desde el resto de nodos al origen:\r\n").getBytes());

  	  		for(int d = 0; d < D.length; d++) {
            if(o == d) continue;
  	  			int ini = d;
  			  	oe.write(new String("[" + ini + "]").getBytes());
  				  do {
  					  oe.write(new String(" -- " + D[o][ini] + " --> [" + P[o][ini] + "]").getBytes());
  					  ini = P[o][ini];
  				  } while(ini != o);
  				  oe.write(new String("\r\n").getBytes());
  			  }
    			oe.write(new String("\r\n").getBytes());        
        }
  		} catch(Exception e) {
  			e.printStackTrace();
  		}
  	}
	}

	public FloydResult AlgFloyd(Grafo G) {
		FloydResult Result = new FloydResult(G);
		
	  for(int i = 0; i < G.NumVertices; i++) {
	    for(int j = 0; j < G.NumVertices; j++) {
	      if(G.EstaConectado(i, j))	Result.P[i][j] = i;
	      Result.D[i][j] = (G.EstaConectado(i, j)) ? G.ObtenerArista(i, j).weight : Integer.MAX_VALUE;
	    }
	  }		
		
		for(int k = 0; k < G.NumVertices; k++) {
			for(int i = 0; i < G.NumVertices; i++) {
				for(int j = 0; j < G.NumVertices; j++) {
          int IK = Result.D[i][k];
          int KJ = Result.D[k][j];
          int IJ = Result.D[i][j];
			    if ((IJ > IK + KJ) && (IK < Integer.MAX_VALUE) && (KJ < Integer.MAX_VALUE)) {
 					  Result.D[i][j] = IK + KJ;
 					  Result.P[i][j] = Result.P[k][j];
			    }
			  }   
			}
		}
		return Result;
	}
}