public LinkedList<E> RutaMasCortaDijkstra(E v_origen, E v_destino) { int[][] matrizAdyacentes = matriz_adyac;//copio la matriz de adyacencia.
int[] posVertPadre = new int[list_vertices.size()];//va a guardar en el array como valor interno la pos del vertice padre de acuerdo a su posicion(posision en el array es la delvertice hijo) en este array.
LinkedList<Vertice<E>> listVertVisitados = list_vertices;//lista q va a ir eliminando los vertices que sean visitados
LinkedList<E> ruta;
//inicializo todos los valores de la diagonal de la matriz en el valor mas alto posible
for (int i = 0; i < matrizAdyacentes.length; i++) { matrizAdyacentes[i][i] = 9999999;
}
//inicializo el grado del vertice de origen en 0;
matrizAdyacentes[PosVertice(v_origen)][PosVertice(v_origen)] = 0;
BuscarRutaMasCortaR(v_origen, v_destino, matrizAdyacentes, listVertVisitados, posVertPadre);
ruta = ConstruirCamino(posVertPadre, v_origen, v_destino);//a ruta le asigno la lista de la ruta que devuelve el metodo.
costoDijkstra=0;//variable creada en el constructor de la clase
for (int i = 0; i < ruta.size(); i++) { for (int j = 1; j < ruta.size(); j++) { costoDijkstra =costoDijkstra+ matriz_adyac[PosVertice(ruta.get(i))][PosVertice(ruta.get(j))];
}
}
ruta.descendingIterator();//invierte la lista
return ruta;
}
public int[] BuscarRutaMasCortaR(E v_actual, E v_destino, int[][] matrizAdyacentes, LinkedList<Vertice<E>> listVertVisitados, int[] posVertPadre) { //FORMULA: Min{L(x),L(v)+w(v,x)}, T{lista de vertices}, V=vertice actual q se esta visitando
if (v_actual.equals(v_destino) || listVertVisitados.isEmpty()) { return posVertPadre;//retorna el arreglo
} else { //declaracion de variables
int suma = 0;//guarda la distancia desde el valor del vertice+peso de la arista.
int min = 0;//guarda el valor minimo encontrado en la formula
int temp = 9999999;
//comenzando
//lo siguiente busca en los adyacentes al vertice de origen el de menor distancia
for (Vertice v : ListVertDestino(v_actual)) { //ahora suma el valor del vertice q se esta visitando(actual) con el peso de la arista entre el que se esta visitando y el adyacente actual en que esta parado el for.
suma = matrizAdyacentes[PosVertice(v_actual)][PosVertice(v_actual)] + matrizAdyacentes[PosVertice(v_actual)][v.getPos()];
min = Math.min(matrizAdyacentes[PosVertice(v_actual)][PosVertice(v_actual)], suma);//busca el minimo entre el vertice q se esta parado en el for y el de la suma anterior
matrizAdyacentes[v.getPos()][v.getPos()] = min;//en la diagonal de la matriz guarda el grado que va tomando cada vertice, si el valor actual es mayor lo cambia por el nuevo que es menor.
posVertPadre[v.getPos()] = PosVertice(v_actual);//a la pos del vertice hijo le asigno la pos del vertice padre(el que le dio el valor)
}
listVertVisitados.remove(PosVertice(v_actual));//como es visitado lo saco de la lista.
//recorrer la lista de vertices visitados y buscar el de menor grado y volver a hacer lo mismo hasta que los vertices actual y visitado sean el mismo o que la lista de visitados este vacia.
for (Vertice v : listVertVisitados) { if (matrizAdyacentes[v.getPos()][v.getPos()] < temp) {//si es menor
temp = v.getPos();//guardo la pos del vertice menor
}
}
return BuscarRutaMasCortaR((E) list_vertices.get(temp), v_destino, matrizAdyacentes, listVertVisitados, posVertPadre);
//la E es para castear.
}
}
public LinkedList<Vertice> ListVertDestino(E v_origen) {//devuelve una lista de vertices de destino a uno dado como origen.
LinkedList<Vertice> listdestino = new LinkedList<>();
for (int i = 0; i < matriz_adyac.length; i++) { if (matriz_adyac[PosVertice(v_origen)][i] != -1) { listdestino.add(list_vertices.get(i));
}
}
return listdestino;
}
public LinkedList<E> ConstruirCamino(int[] posVertPadre, E v_origen, E v_destino) { LinkedList<E> aux = new LinkedList<>();//list q guarda la ruta de atras para alante
int posVertAnterior = -1;//variable temporal para moverse por el arreglo de vertices padres
aux.add(v_destino);//añade vertice de destino
return ConstruirCaminoR(posVertPadre, v_origen, v_destino, aux, posVertAnterior);
}
//recursivo
public LinkedList<E> ConstruirCaminoR(int[] posVertPadre, E v_origen, E v_destino, LinkedList<E> aux, int posVertAnterior) { if (posVertAnterior == PosVertice(v_origen)) { aux.add(v_origen);//añade vertice de origen antes de devolverla
return aux;
} else { posVertAnterior = posVertPadre[PosVertice(v_destino)];//a pospadre le asigno la pos del vertice adyacente al destino que le dio el valor
aux.add((E) list_vertices.get(posVertAnterior));//añade el vertice a la lista
return ConstruirCaminoR(posVertPadre, v_origen, (E) list_vertices.get(posVertAnterior), aux, posVertAnterior);
}
}
Crear cuenta
Comentarios sobre la versión: 1.0 (0)
No hay comentarios