Algorithm by Dijkstra

Question

I’m trying to implement a maze, where one needs to find a better way to get to the exit (without running into the wall). The labyrinth has already been implemented, the structure is practically ready (it runs through the whole labyrinth).

But I would like him to travel only from entrance to exit, and for that I used Dijkstra to make this journey.

Follow the classes and their codes:

Labyrinth class:

import java.util.Collections;
import java.util.Arrays;

public class Labirinto {
    private final int x;
    private final int y;
    private final int[][] maze;
    private static char[][] drawnMaze;

    private static Grafo grafoLabirinto;



    private final static int TAMANHO = 4; //PARA AUMENTAR O TAMANHO DO LABIRINTO, BASTA MODIFICAR ESTA VARIÁVEL.




    private final static int ENTRADAX = 0;
    private final static int ENTRADAY = 1;
    private final static int SAÍDAX = (TAMANHO*2);
    private final static int SAÍDAY = (TAMANHO*2-1);





    public Labirinto(int x, int y) {
        this.x = x;
        this.y = y;
        maze = new int[this.x][this.y];
        drawnMaze = new char [TAMANHO*2+1][TAMANHO*2+1];
        generateMaze(0, 0);
    }

Class Edge:

public class Aresta {

        private Vértice origem;
        private Vértice destino;

       public Aresta(Vértice origem, Vértice destino) {
            this.origem = origem;
            this.destino = destino;
        }


        public Vértice getOrigem(){
            return this.origem;
        }

        public Vértice getDestino(){
            return this.destino;
        }

    }

Classe Vertice:

import java.util.ArrayList;


public class Vértice {

    private String id;
    int x;
    int y;
    private ArrayList <Aresta> adj;


    public Vértice(String id, int x, int y){
        this.id = id;
        this.x = x;
        this.y = y;
        this.adj = new ArrayList <Aresta>();
    }

      public void addAdj(Aresta e) {
            adj.add(e);
            System.out.println(adj.size());
        }

    public String getId(){
        return this.id;
    }

    public int getX(){
        return this.x;
    }

    public int getY(){
        return this.y;
    }


    public ArrayList <Aresta> getArestas(){
        return adj;
    }

}

Dijkstra class:

/*
 * Classe para calular o caminho minimo entre dois vértices
 * Usando o algoritmo de Dijkstra
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Dijkstra {

    // Atributos usados na funcao encontrarMenorCaminho

    Vértice menorCaminho = new Vértice(null, 0, 0);

    // Variavel que recebe os vértices pertencentes ao menor caminho
    Vértice verticeCaminho = new Vértice(null, 0, 0);

    // Variavel que guarda o vértice que esta sendo visitado
    Vértice atual = new Vértice(null, 0, 0);

    // Variavel que marca o vizinho do vértice atualmente visitado
    Vértice vizinho = new Vértice(null, 0, 0);

    // Lista dos vertices que ainda nao foram visitados
    List<Vértice> naoVisitados = new ArrayList<Vértice>();

    // Algoritmo de Dijkstra
    public List<Vértice> encontrarMenorCaminhoDijkstra(Grafo grafo, Vértice v1,
            Vértice v2) {

        // Adiciona a origem na lista do menor caminho
        menorCaminho.getId();

        // Colocando a distâncias iniciais
        for (Grafo ) {

            // Vértice atual tem distância zero, e todos os outros,
            // ("infinita - qualquer valor")
            if (grafo.getVertices().get(i).getDescricao()
                    .equals(v1.getDescricao())) {

                grafo.getVertices().get(i).setDistancia(0);

            } else {

                grafo.getVertices().get(i).setDistancia(9999);

            }
            // Insere o vertice na lista de vertices nao visitados
            this.naoVisitados.add(grafo.getVertices().get(i));
        }

        Collections.sort(naoVisitados);

        // O algoritmo continua ate que todos os vertices sejam visitados
        while (!this.naoVisitados.isEmpty()) {

            // Toma-se sempre o vertice com menor distancia, que eh o primeiro
            // da
            // lista

            atual = this.naoVisitados.get(0);
            System.out.println("Pegou esse vertice:  " + atual);
            /*
             * Para cada vizinho (cada aresta), calcula-se a sua possivel
             * distancia, somando a distancia do vertice atual com a da aresta
             * correspondente. Se essa distancia for menor que a distancia do
             * vizinho, esta eh atualizada.
             */
            for (int i = 0; i < atual.getArestas().size(); i++) {

                vizinho = atual.getArestas().get(i).getDestino();
                System.out.println("Olhando o vizinho de " + atual + ": "
                        + vizinho);
                if (!vizinho.verificarVisita()) {

                    // Comparando a distância do vizinho com a possível
                    // distância
                    if (vizinho.getDistancia() > (atual.getDistancia() + atual
                            .getArestas().get(i).getPeso())) {

                        vizinho.setDistancia(atual.getDistancia()
                                + atual.getArestas().get(i).getPeso());
                        vizinho.setPai(atual);

                        /*
                         * Se o vizinho eh o vertice procurado, e foi feita uma
                         * mudanca na distancia, a lista com o menor caminho
                         * anterior eh apagada, pois existe um caminho menor
                         * vertices pais, ateh o vertice origem.
                         */
                        if (vizinho == v2) {
                            menorCaminho.clear();
                            verticeCaminho = vizinho;
                            menorCaminho.addAdj(vizinho);
                            while (verticeCaminho.getPai() != null) {

                                menorCaminho.add(verticeCaminho.getPai());
                                verticeCaminho = verticeCaminho.getPai();

                            }
                            // Ordena a lista do menor caminho, para que ele
                            // seja exibido da origem ao destino.
                            Collections.sort(menorCaminho);

                        }
                    }
                }

            }
            // Marca o vertice atual como visitado e o retira da lista de nao
            // visitados
            atual.visitar();
            this.naoVisitados.remove(atual);
            /*
             * Ordena a lista, para que o vertice com menor distancia fique na
             * primeira posicao
             */

            Collections.sort(naoVisitados);
            System.out.println("Nao foram visitados ainda:"+naoVisitados);

        }

        return menorCaminho;
    }

}






    public static void main(String[] args) {
        int x = args.length >= 1 ? (Integer.parseInt(args[0])) : TAMANHO;
        int y = args.length == 2 ? (Integer.parseInt(args[1])) : TAMANHO;
        Labirinto maze = new Labirinto(x, y);
        maze.display();
        //maze.displaySkeleton();
        maze.displayStringMaze();

        grafoLabirinto = BFS.gerarGrafo(new Vértice("0", 0, 1), drawnMaze);
        System.out.println(grafoLabirinto.toString());
    }








    public void displaySkeleton(){
        for(int i=0; i < maze.length; i++){
            for(int j=0; j < maze.length; j++){
                System.out.print(maze[i][j]);
            }
            System.out.println("");
        }

    }

    public void displayStringMaze(){
        for(int i=0; i < TAMANHO*2+1; i++){
            for(int j=0; j < TAMANHO*2+1; j++){
                System.out.print(drawnMaze[i][j]);
            }
            System.out.println("");
            }
        }






    public void display() {

        int lineIterator = 0;
        int colIterator = -1;

        for (int i = 0; i < y; i++) {

            // draw the north edge
            for (int j = 0; j < x; j++) {   
                if((maze[j][i] & 1) == 0){
                    drawnMaze[lineIterator][++colIterator] = '█';
                    drawnMaze[lineIterator][++colIterator] = '█';
                }else{
                    drawnMaze[lineIterator][++colIterator] = '█';
                    drawnMaze[lineIterator][++colIterator] = ' ';
                }
            }
            drawnMaze[lineIterator++][++colIterator] = '█';
            colIterator = -1;


            // draw the west edge
            for (int j = 0; j < x; j++) {

                if((maze[j][i] & 8) == 0){
                    drawnMaze[lineIterator][++colIterator] = '█';
                    drawnMaze[lineIterator][++colIterator] = ' ';
                }else{
                    drawnMaze[lineIterator][++colIterator] = ' ';
                    drawnMaze[lineIterator][++colIterator] = ' ';
                }
            }
            drawnMaze[lineIterator++][++colIterator] = '█';
            colIterator = -1;

        }


        // draw the bottom line
        for (int j = 0; j < x; j++) {

            drawnMaze[lineIterator][++colIterator] = '█';
            drawnMaze[lineIterator][++colIterator] = '█';

        }

        drawnMaze[lineIterator][++colIterator] = '█';

        //draw entrance & exit
        drawnMaze[ENTRADAX][ENTRADAY] = 'e';
        drawnMaze[SAÍDAX][SAÍDAY] = 's';

    }


    private void generateMaze(int cx, int cy) {
        DIR[] dirs = DIR.values();
        Collections.shuffle(Arrays.asList(dirs));
        for (DIR dir : dirs) {
            int nx = cx + dir.dx;
            int ny = cy + dir.dy;
            if (between(nx, x) && between(ny, y)
                    && (maze[nx][ny] == 0)) {
                maze[cx][cy] |= dir.bit;
                maze[nx][ny] |= dir.opposite.bit;
                generateMaze(nx, ny);
            }
        }
    }

    private static boolean between(int v, int upper) {
        return (v >= 0) && (v < upper);
    }

    private enum DIR {
        N(1, 0, -1), S(4, 0, 1), E(4, 1, 0), W(8, -1, 0);
        private final int bit;
        private final int dx;
        private final int dy;
        private DIR opposite;

        // use the static initializer to resolve forward references
        static {
            N.opposite = S;
            S.opposite = N;
            E.opposite = W;
            W.opposite = E;
        }

        private DIR(int bit, int dx, int dy) {
            this.bit = bit;
            this.dx = dx;
            this.dy = dy;
        }
    };

/*  
    public static void encontraCaminho(){ 
          int k = 0;
          int pos;
          int aux = 0;
          for(int i = 0; i < TAMANHO ; i ++){
            for(int j = 0; j<TAMANHO-1;j++){
              if(k==0){ //verificando se é a primeira execução
                k++;
                grafoLabirinto[ENTRADAX][ENTRADAY] = 2; // mudar espaço vago para um espaço percorrido
                grafoLabirinto[SAÍDAX][SAÍDAY] = 2;
                j = ENTRADAY;
                i = ENTRADAX;
              }
              if(grafoLabirinto == 0){
                grafoLabirinto[i][j] = 2;
                if(grafoLabirinto[i][j+1]==0){
                    aux++;
                }else if(grafoLabirinto[i+1][j]==0){
                    aux++;
                }else if(grafoLabirinto[i-1][j]==0){
                    aux++;
                }
              }
            }
          }
        }
 */


}

This is a simple example of graph implementation represented by adjacency list:

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

public class Grafo {

    List<Vértice> vértices;
    List<Aresta> arestas;

    public Grafo() {
        vértices = new ArrayList<Vértice>();
        arestas = new ArrayList<Aresta>();
    }

    public Vértice addVertice(Vértice v) {
        v = new Vértice(v.getId(), v.getX(), v.getY());
        vértices.add(v);
        return v;
    }

    public Aresta addAresta(Vértice origem, Vértice destino) {
        Aresta e = new Aresta(origem, destino);
        arestas.add(e);
        return e;
    }

    public String arestasToString(){
        String s = "";
        for(Aresta a: arestas){
            s += "{" + a.getDestino().getId() +" , " +a.getOrigem().getId() + "}";
        }
        return s;
    }

    public String toString() {
        String r = "";

        for (Vértice u : vértices) {
            r+= String.format("%s (%d,%d) -> ", u.getId(), u.getX(), u.getY());
            //r += u.getId() + " " + u.getX() +" -> ";

            for (Aresta e : u.getArestas()) {
                Vértice v = e.getDestino();
                r += v.getId() + ", ";
            }

            r += "\n";

        }

        return r;
    }

    public void ligarArestas(){
        for(Vértice v : vértices){
            for(Aresta a : arestas){
                if(v.getId()==a.getOrigem().getId()){
                    v.getArestas().add(a);
                }
            }
        }
    }



    /*
    public static void main(String[] args) {
        Grafo g = new Grafo();
        Vertice s = g.addVertice("s");
        Vertice t = g.addVertice("t");
        Vertice y = g.addVertice("y");
        Aresta st = g.addAresta(s, t);
        Aresta sy = g.addAresta(s, y);
        Aresta ty = g.addAresta(t, y);
        Aresta yt = g.addAresta(y, t);
        System.out.println(g);
    }

    */
}

My question is: how do I implement the class Dijkstra in this context of the labyrinth, where I only need to follow from the entrance to the exit (without going through the dead ends)?