7

Lo que sucede es que ya tengo implementado mi algoritmo de Dijkstra en Java, tengo un arreglo llamado dist que contiene el costo menor para llegar a cada uno de los nodos. El nodo origen lo paso como parámetro en mi función junto con mi matriz adyacente y el número de nodos.

El problema es que no puedo mostrar el camino que sigue el algoritmo para llegar al camino mas corto, necesito saber las coordenadas de los nodos por los que pasa e imprimirlo.

 public int[] dijkistra( int inicio, int maxvertices, Object[][] matrix) {
     int[] distancia = new int[maxvertices+1];
     int[] padre = new int[maxvertices+1];
     boolean[] visto = new boolean[maxvertices+1];
     for (int i = 1; i < maxvertices+1; i++) {
         distancia[i] = 1200000000;
         padre[i] = -1;
        visto[i] = false;
     }
     distancia[inicio]=0;
     PriorityQueue<Integer> pila = new PriorityQueue<>();
     pila.add(distancia[inicio]+1);
     while (!pila.isEmpty()) {
        int u = pila.poll();
        visto[u] = true;

     for (int i = 1; i < maxvertices+1; i++) { 
         if ( (Integer)matrix[u][i] != 0) {
             if (distancia[i] > distancia[u] + (Integer)matrix[u][i]) {  
                distancia[i] = distancia[u] + (Integer)matrix[u][i];
                System.out.print("| "+matrix[u][i]+" u:"+u+" i:"+i);
                padre[i] = u;
                pila.add(i);
             }
         }
    }
 }
return distancia;
}
2
  • que es camino en la funcion imprimir
    – user112828
    Commented el 31 dic. 2018 a las 4:24
  • Me podrían explicar como funciona este programa? .__. Commented el 10 oct. 2019 a las 0:00

4 respuestas 4

1

Efectivamente las respuestas anteriores son todas correctas. Añadiría además que con cualquier algoritmo de optimización combinatoria como este, se persigue el valor de la función objetivo, ignorando deliberadamente que ese valor se puede producir en distintos puntos (un punto es un vector con el conjunto de valores finales para las variables). Eso es, el camino más corto no tiene por qué ser único.

Y en cualquiera de las técnicas que uses, ya sea programación dinámica como estás haciendo, o por ramificación y poda o incluso con algoritmos voraces, se deben mantener estructuras adicionales (normalmente árboles de precedencias como es el caso) para recuperar el punto (los valores de las aristas) en donde se produce el óptimo encontrado.

0

La primero, tu algoritmo tiene un pequeño fallo, justo después de inicializar la cola estas poniendo:

pila.add(distancia[inicio]+1); 

Y debería ser el incio, ya que debes empezar siempre por este nodo:

pila.add(distancia[inicio]);

Ahora, para imprimir el camino hasta un determinado nodo desde el inicio, como ya tienes un array donde vas guardando cual es el mejor nodo para ir hasta el actual (parde[]), simplemente tienes que crear una función recursiva que utilice este array para ir imprimiendo el camino:

public void imprimirCamino(int[] padre, int inicio, int destino){
     if(destino == 0){
         System.out.println(destino);
     } else {
         camino(padre, inicio, padre[destino]);
         System.out.println(destino);
     }       
 }

Y llamas a esta función con el inicio (que siempre será el mismo que hayas pasado a tu funcion dijkstra) y el destino al que quieres llegar. Por ejemplo, para mostrar el mejor camino hasta 3:

imprimirCamino(padre, inicio, 3);
0

Totalmente de acuerdo con la respuesta de Wyrncael.

Añadiría además, y siendo ya muy quisquilloso, que al inicializar la distancia en la matrix no lo hagas con 1200000000, sino con Integer.MAX_VALUE.

for (int i = 1; i < maxvertices+1; i++) {
    distancia[i] = Integer.MAX_VALUE;
    padre[i] = -1;
    visto[i] = false;
}

Es poco probable que tengas distancias tan grandes, pero no cuesta nada cambiarlo y cubres todos los posibles casos con distancias comprendidas en el rango de int

0

Espero le sirva a alguien !

import java.util.*;

public class Dijkstra {

public int[] distancia = new int[10];
public int[][] costo = new int[10][10];

public void calc(int n, int s) {
    int[] bandera = new int[n + 1];
    int i, minpos = 1, k, c, minima;

    for (i = 1; i <= n; i++) {
        bandera[i] = 0;
        this.distancia[i] = this.costo[s][i];
    }
    c = 2;
    while (c <= n) {
        minima = 99;
        for (k = 1; k <= n; k++) {
            if (this.distancia[k] < minima && bandera[k] != 1) {
                minima = this.distancia[i];
                minpos = k;
            }
        }
        bandera[minpos] = 1;
        c++;
        for (k = 1; k <= n; k++) {
            if (this.distancia[minpos] + this.costo[minpos][k] < this.distancia[k] && bandera[k] != 1) {
                this.distancia[k] = this.distancia[minpos] + this.costo[minpos][k];
            }
        }
    }

}

public static void main(String args[]) {
    int nodos, posicion, i, j;
    Scanner sc = new Scanner(System.in);
    System.out.println("Ingrese el número de nodos \n");
    nodos = sc.nextInt();
    Dijkstra d = new Dijkstra();
    System.out.println("Ingrese los pesos de la matriz de costos: \n");
    for (i = 1; i <= nodos; i++) {
        for (j = 1; j <= nodos; j++) {
            d.costo[i][j] = sc.nextInt();
            if (d.costo[i][j] == 0) {
                d.costo[i][j] = 999;
            }
        }
    }
    System.out.println("Ingrese la posicion de origen :\n");
    posicion = sc.nextInt();

    d.calc(nodos, posicion);
    System.out.println("El camino más corto desde la posicion \t" + posicion + "\t a todos los demás puntos son : \n");
    for (i = 1; i <= nodos; i++) {
        if (i != posicion) {
            System.out.println("posicion :" + posicion + "\t destino :" + i + "\t Costo minimo es :" + d.distancia[i] + "\t");
        }
    }

}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.