Código de Java - Codigo de la ruta mas corta, DIJKSTRA

Imágen de perfil

Codigo de la ruta mas corta, DIJKSTRAgráfica de visualizaciones


Java

estrellaestrellaestrellaestrellaestrella(7)
Publicado el 20 de Junio del 2016 por Hugo L
35.659 visualizaciones desde el 20 de Junio del 2016
Este es el Dijkstra, lo hice basado en los ejercicios resueltos de forma analítica, lo pongo a disposición de ustedes para que lo revicen y en caso de ser necesario optimizarlo, espero que les sirva de algo, casi todas sus lineas están comentadas, cualquier error comentármelo y buscaremos la solución.

Requerimientos

Este código se realizo en una Pc con Win8.1, la plataforma de programación es el Netbeans 8.0.2, con el jdk 7.1

1.0

Publicado el 20 de Junio del 2016gráfica de visualizaciones de la versión: 1.0
823 visualizaciones desde el 20 de Junio del 2016
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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);
        }
    }



Comentarios sobre la versión: 1.0 (0)


No hay comentarios
 

Comentar la versión: 1.0

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

2.0
estrellaestrellaestrellaestrellaestrella(7)

Publicado el 21 de Junio del 2016gráfica de visualizaciones de la versión: 2.0
34.837 visualizaciones desde el 21 de Junio del 2016
http://lwp-l.com/s3557