/**
 * rutaCortaApp.java
 */
package pruebaKommit;

import java.util.ArrayList;
import java.util.List;

/**
 * <b>Descripción:<b> Clase que determina
 * <b>Caso de Uso:<b>
 * @author JuanAndres Lopez Osorio
 * @version
 */
public class rutaCortaApp {

	/**
	 * Metodo encargado de
	 * <b>Caso de Uso</b>
	 * @author Juan Andres Lopez Osorio
	 *
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[][] costos= {{-1,30,-1,-1,-1},{-1,-1,30,10,-1},{-1,-1,-1,-1,80},{-1,-1,-1,-1,40},{-1,-1,-1,-1,-1}};
		String [] ciudades= {"Manizales","Pereira","Armenia","Cartago","Cali"};

		ArrayList<String> ciudadesVisitadas=new ArrayList<String>();
		ciudadesVisitadas.add(ciudades[0]);

		ArrayList<Integer>Acostos=new ArrayList<Integer>();
		int i=0;


		//identificaCaminos(costos,ciudades,0,ciudades.length-1,0,0);
		ArrayList<Integer> minimos=menores(costos,ciudades,ciudadesVisitadas);
		ArrayList<String> finalC =buscaCamino(costos, ciudades,ciudadesVisitadas,Acostos,i,minimos);
		for (String string : finalC) {
			System.out.println(string);
		}

	}
	/**
	 * Metodo encargado de descubrir los menores con el finde ayudar en la eleccion de las opciones
	 * <b>Caso de Uso</b>
	 * @author Juan Andres Lopez Osorio
	 *
	 * @param costos son los costos
	 * @param ciudades son las ciudades que se deben introducir
	 * @param ciudadesVisitadas son las ciudades visitadas de acuerdo al menor recorrido
	 * @return ArrayList con los valores menores de cada fila
	 */
	public static ArrayList<Integer> menores(int [][]costos,String [] ciudades,ArrayList<String>ciudadesVisitadas) {
		ArrayList<Integer> menores=new ArrayList<Integer>();
		for ( int i = 0; i < costos.length; i++ )
		    {
		        int min = Integer.MAX_VALUE;
		        for ( int j = 0; j < costos [ i ].length; j++ )
		            if ( costos [ i ] [ j ] < min && (costos [ i ] [ j ]!=-1  ))
		                min=costos [ i ] [ j ];
		        		menores.add(min);
		    }return menores;

	    }


	/**
	 * Metodo encargado de  buscar el mejor camino de acuerdo al menor peso
	 * <b>Caso de Uso</b>
	 * @author Juan Andres Lopez Osorio
	 *
	 * @param costos son los costos
	 * @param ciudades son las ciudades disponibles
	 * @param ciudadesVisitadas son las ciudades visitadas
	 * @param Acostos un Array con los costos finales con los que se determina la ganancia
	 * @param i las filas
	 * @param minimos el array de los mejores rendimientos
	 * @return
	 */
	public static ArrayList<String> buscaCamino(int [][]costos,String[] ciudades, ArrayList<String>ciudadesVisitadas,ArrayList<Integer>Acostos,int i,ArrayList<Integer>minimos) {


		for (int j = 0; j < ciudades.length; j++) {
			if(costos[i][j]!=-1) {
				int aux=costos[i][j];
				if(aux==minimos.get(i)) {
					Acostos.add(costos[i][j]);
					ciudadesVisitadas.add(ciudades[j]);
					i=j;
				}else {
					continue;
				}

			}
		}
	return ciudadesVisitadas;

			}
	}