1

Estoy atascado en el algoritmo de Dijkstra para un grafo dirigido con un vértice de origen y uno de destino (con sus respectivos pesos o costos). La cosa es que tengo que hallar el camino mas corto (valga la redundancia), pero solo he logrado que el recorrido vaya por el camino mas corto de cada nodo, no de todo el grafo desde el origen hasta el destino. La gracia es usar algo parecido al BFS pero adaptarlo para Dijkstra. Se que tengo que comparar las sumas de todos los caminos que llegan hasta el destino pero no hallo la manera de hacerlo. Tambien tengo entendido que se puede utilizar una cola de prioridad pero la verdad que no tengo idea como o en que parte.

Mi código es el siguiente:

public void caminoCortoBFS (String A, String B, JTextArea jta){
    desmarcarTodos();
   ordenarVerticesAlf();     Arco a;
   float distanciatotal=0;
   Vertice v = buscarVertice(A), w;
   LinkedList <Vertice> C;
   C=new LinkedList<Vertice>();
   C.add(v);    
   v.marcado=true;      jta.append("Camino mas corto de " + A + "a " + B + " es: ");
   do{
       v = C.pop();
       jta.append(v.getNombre() + " ");
       for (int i = 0; i < v.LArcos.dim(); i++) { 
           a = (Arco) v.LArcos.getElem(i);
           if(a.getCosto() == minDistancia(v)){
               distanciatotal+=minDistancia(v);
               w=buscarVertice(a.getNombreVertD());
               if(w.nombre.equals(B)){
                   jta.append(w.getNombre() + " " + "\n");
                   jta.append("Distancia total = " + distanciatotal);
                   return;}
                if (!w.marcado) {
               C.add(w);
               w.marcado=true;
                }

           }
       
       }
      
   }while (!C.isEmpty());
}



private float minDistancia(Vertice A){
    float distMinima=99999; Arco a;
    for(int i=0; i<A.LArcos.dim(); i++){
        a = (Arco) A.LArcos.getElem(i);
        if(a.getCosto()<distMinima)
            distMinima=a.getCosto();
    }
    return distMinima;
}

Y como resultado para el siguiente grafo: introducir la descripción de la imagen aquí

Me da como resultado poniendo como vértices Origen A - Destino D :

A -> C -> E -> D

Cuando deberia ser A -> B -> D

Se que esta fatal, pero agradecería cualquier ayuda que pudieran darme.

2 respuestas 2

0

BFS y Dijkstra son distintos algoritmos. En BFS usas una pila para contener una lista de nodos y recorrerlos sistemáticamente por profundidad. En Dijkstra usas una cola de prioridades para hacer lo mismo e ir corrigiendo las cantidades calculadas hasta tener los costos (distancias) calculados para todos los nodos.

El algoritmo de Dijkstra generalmente se resuelve con una lista de adyacencia para representar el grafo.

Es decir tenemos un ArrayList1 que apunta a listas de vertices2 adyacentes. Es decir puedes usar algo como:

List<List<Vertice>> listaAdyacencia = new ArrayList<>(numVertices);

Ahora después de inicializar tu lista de adyacencia, generalmente se tiene que tener una cola de prioridades para los costos. Llámalo costos por ejemplo. El PriorityQueue de Java es muy básico, no te deja encontrar un item y cambiarle de prioridad por ejemplo, por lo que tienes que implementar el tuyo propio, usar otra librería no estándar, o tienes que usar una lista que es considerablemente menos eficiente.

Entonces los pasos del algoritmo son:

 1. Empieza considerando todos los costos de cada vertice Integer.MAX_VALUE (es decir: Infinito)
 2. Inicializa el costo del vértice de origen a 0
 3. Inicializa una cola de prioridades **costos** y agrega todo los vertices con sus costos respectivos
 4. Mientras hayan nodos desconocidos en el grafo
    1. Selecciona el nodo deconocido N con el menor costo
    2. Marca N como conocido
    3. Para cada nodo A adyacente a N
       If (costo[N] + costo de ir de N a A < costo[A])
          costo[A] = costo[N] + costo de ir de N a A
          anterior[A] = N    // esto te ayuda a reconstruir el camino

Para mayor información puedes ver este PDF: https://courses.cs.washington.edu/courses/cse373/01sp/Lect24_4up.pdf

1 ArrayList es generalmente mejor que LinkedList en Java por varios motivos pero eso es tema de otro articulo.

2 también llamados nodos

9
  • Resulta que los costos los tengo en una clase llamada "Arco", que contiene el costo del mismo y el vértice de destino (a donde apunta), ya que no almaceno los costos en cada vértice directamente ¿aplicaría la misma lógica con esto? Commented el 18 jun. 2020 a las 5:17
  • Hay 2 costos.. hay un costo que es el costo asociado con cada vértice. Por ejemplo el costo de ir del origen al origen es 0. El otro costo es el costo de pasar por un Arco que esta en tu clase Arco. Para implementar eso como lista de adyacencia tienes que hacer algo como: List<List<CostoYVertice<Integer,Vertice>>> listaAdyacencia = new ArrayList<>(); O tienes que hacer una lista de "Arco"s suponiendo que Arco apunta al vertice de destino. Pero lo comun seria numerar vertices, y guardar costos asociados con cada transicion en la lista de adyacencia misma.
    – AminM
    Commented el 18 jun. 2020 a las 5:23
  • Claro, en mi clase "Arco" se encuentra el vértice al que apunta un arco. Manejo los arcos como listas pertenecientes a cada vértice/nodo. Lo que me tiene dando vueltas es la manera de hallar el camino mas corto del grafo desde un origen a un destino, pero que no tome las rutas más pequeñas de cada nodo individual, sino del grafo en general. Y como no tengo presente la idea de listas de adayencias o colas de prioridad se me hace muy complicado. Commented el 18 jun. 2020 a las 5:39
  • Si no usas la estructura de datos correcta para el problema, tu solución no será optima. No puedes implementar Dikjstra EFICIENTEMENTE sin cola de prioridades. Y no convenientemente sin Listas de Adyacencia o Tablas de Adjacencia. Usar objetos Vertice y Arcos no son la mejor forma de representar grafos para este tipo de algoritmos.
    – AminM
    Commented el 18 jun. 2020 a las 5:42
  • El mayor problema es hacer para saltar de vertice a vertice en el grafo. Es posible supongo.. pero sucio.
    – AminM
    Commented el 18 jun. 2020 a las 5:43
0

Comparto , no se si resuelva el problema espero que si ! saludos !!

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.