ajuda, meu Djikstra está pegando muito mais caminhos do que o necessário

para mais informações, segue toda a minha classe onde o algoritmo Djikstra e Yen (k-shortest paths) está implementada

package grafo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class Grafo {
    private Map<String, Vertice> vertices;
    private Map<String, Aresta> arestas;

    public Grafo() {
        this.vertices = new HashMap<>();
        this.arestas = new HashMap<>();
    }

    public void addArestas(Aresta a) {
        this.arestas.put(a.getId(), a);
    }

    public void addVertices(Vertice v) {
        this.vertices.put(v.getId(), v);
    }

    public Aresta[] getArestas() {
        Aresta a[] = new Aresta[arestas.values().size()];
        return arestas.values().toArray(a);
    }

    public Vertice[] getVertices() {
        Vertice v[] = new Vertice[vertices.values().size()];
        return vertices.values().toArray(v);
    }

    public Aresta[] Djikstra(Vertice inicial, Vertice destino) {
        List<Aresta> Caminho = new ArrayList<>();
        PriorityQueue<DijkstraVertice> Unvisited = new PriorityQueue<>();
        DijkstraVertice unv[];
        DijkstraVertice current = null;


        for (Vertice v : this.getVertices()) {
            Unvisited.add(new DijkstraVertice(v));

        }

        unv = new DijkstraVertice[Unvisited.size()];
        unv = Unvisited.toArray(unv);

        for (DijkstraVertice v : unv) {
            if (v.equals(inicial)) {
                current = v;
                current.setMinPeso(0.0);
                Unvisited.remove(inicial);
            }
        }

        while (!Unvisited.isEmpty()) {
            for (Aresta a : this.getArestas()) {
                if (a.getInicio().equals(current) || (a.isTwo_way() && a.getFim().equals(current))) {
                    unv = new DijkstraVertice[Unvisited.size()];
                    unv = Unvisited.toArray(unv);

                     for (DijkstraVertice v : unv) {
                        if (v.equals(a.getFim()) || (a.isTwo_way() && v.equals(a.getInicio()))) {
                            if (v.setMinPeso(a.getPeso())) {
                                Unvisited.remove(v);
                                Unvisited.add(v);
                            }
                        }
                    } 
                }
            }
            DijkstraVertice prev = current;
            current = Unvisited.poll();
            current.setPrev(prev);

            if (current.equals(destino)) {
                int v=0;
                while (current.getPrev() != null) {
                    for (Aresta a : this.getArestas()) {
                        if ((a.getInicio().equals(current) && a.getFim().equals(current.getPrev()))
                                || (a.getFim().equals(current) && a.getInicio().equals(current.getPrev()))) {
                            Caminho.add(a);
                            System.out.println(v++ + " -- " + a.getInicio().getId() + " -> " + a.getFim().getId() + " " + a.getRede());
                            break;
                        }
                    }
                    current = current.getPrev();
                }

                Collections.reverse(Caminho);
                Unvisited.clear();
            }
        }

        Aresta path[] = new Aresta[Caminho.size()];
        return Caminho.toArray(path);
    }

    public Aresta[][] Yen(Vertice inicial, Vertice destino, int K) {
        System.out.println("oi");
        Aresta[][] A = new Aresta[K][];
        A[0] = this.Djikstra(inicial, destino);
        PriorityQueue<Aresta[]> B = new PriorityQueue<>(new Comparator<Aresta[]>() {

            @Override
            public int compare(Aresta[] o1, Aresta[] o2) {
                Double p1 = 0.0, p2 = 0.0;
                for (int i = 0; i < o1.length; i++) {
                    p1 += o1[i].getPeso();
                }
                for (int i = 0; i < o2.length; i++) {
                    p2 += o2[i].getPeso();
                }

                return p1.compareTo(p2);
            }
        });

        for (int k = 1; k < K; k++) {
            System.out.println(k);
            for (int i = 1; i < A[k - 1].length; i++) {
                System.out.println(k + ":" + i);
                ArrayList<Aresta> restoreEdge = new ArrayList<>();
                ArrayList<Vertice> restoreVertex = new ArrayList<>();

                Vertice impulso = A[k - 1][i].getInicio();
                Aresta[] rootPath = Arrays.copyOfRange(A[k - 1], 0, i);

                for (int j = 0; j < k; j++) {
                    if (rootPath.equals(Arrays.copyOfRange(A[j], 0, i))) {
                        restoreEdge.add(A[j][i]);
                        this.arestas.remove(A[j][i].getId());
                    }
                }

                for (int j = 0; j < rootPath.length - 1; j++) {
                    restoreVertex.add(rootPath[j].getInicio());
                    this.vertices.remove(rootPath[j].getInicio().getId());
                }

                Aresta spurPath[] = this.Djikstra(impulso, destino);

                Aresta[] totalPath = new Aresta[rootPath.length + spurPath.length];
                for (int j = 0; j < rootPath.length; j++) {
                    totalPath[j] = rootPath[j];
                }
                for (int j = 0; j < spurPath.length; j++) {
                    totalPath[j + rootPath.length] = spurPath[j];
                }

                B.add(totalPath);
                for (Aresta aresta : restoreEdge) {
                    this.arestas.put(aresta.getId(), aresta);
                }
                for (Vertice vertice : restoreVertex) {
                    this.vertices.put(vertice.getId(), vertice);
                }
            }

            if (B.isEmpty()) {
                return A;
            } else {
                A[k] = B.poll();
            }
        }
        return A;
    }
}

Olá Aderbal!

Fico contente que você esteja implementando o seu próprio Dijkstra! Estou dando uma olhada no código e já comento sobre o que eu puder ajudar!

Olá de novo,

Estou olhando seu código e está um pouco complicado de ir executando ele na cabeça. Você pode subir ele em algum lugar público (por exemplo, o GitHub) ou passar o resto do código (classes Vertice, Aresta, etc)?

Mas pra começar, tenho algumas dicas para dar em relação ao código:

• Quando estamos implementando um algoritmo como esse, precisamos prestar bastante atenção às estruturas de dados. Dependendo da estrutura usada, podemos acabar mudando a complexidade (tempo de execução) do algoritmo sem nem perceber
• Você está meio que "sub-utilizando" o poder da PriorityQueue: A cada chamada de Unvisited.toArray(), você gasta V operações (onde V é o número de vértices) quando não deveria gastar nenhuma. Em uma implementação ótima, você não vai precisar fazer esse .toArray() nenhuma vez.
• Ainda não tenho certeza, mas creio que o problema principal da sua implementação é a repetição da chamada unv = Unvisited.toArray(unv); dentro do for. Isso multiplica o tempo de execução por V e deixa o algoritmo muito lento.
• Outra dica, que serve para qualquer implementação de grafos é que, normalmente, é mais fácil criar duas arestas a->b e b->a do que criar uma aresta e marcar que ela é nas duas direções. Isso acaba removendo a complexidade da sua condição if (a.getInicio().equals(current) || (a.isTwo_way() && a.getFim().equals(current))). Como o seu exemplo é com coordenadas geográficas, talvez faça até sentido uma outra coisa, que é definir que TODAS as arestas são duplas. Aí também fica menos complexo.

Por enquanto é isso, vou continuar olhando o código pra ter certeza da fonte do problema. Vai enviando aqui os avanços que você fizer e também o código fonte completo pra eu poder compilar o programa!

Abraços, Alessandro

Bom dia Alessandro, assim como pedido, aqui está o Git do trabalho em questão

https://github.com/IXXSlashXXI/GPS-Paris--K-Shortest-Path-

Na verdade, a época da entrega do trabalho da faculdade já passou e eu já entreguei o trabalho incompleto, mas mesmo assim quero otimizar o código e pegar o melhor caminho !

Para testar o código, já existem 2 arquivos .csv dentro do mesmo, você deve fazer da seguinte maneira na hora de executar o algoritmo

nessa ordem: caminho para o arquivo de vértices (ESPAÇO) caminho para o arquivo de arestas (ESPAÇO) Vértice Inicial (ESPAÇO) Vértice Final (ESPAÇO) K

Como estamos otimizando primeiramente o Djikstra, coloque K = 1

Vou colocar o exemplo que eu estava usando, originalmente no meu primeiro djikstra que peguei da internet estava dando um caminho de 190, mas esse novo djikstra está dando um caminho de 7400 !

C:\Users\Aderbal\Desktop\Grafos\vertex.csv C:\Users\Aderbal\Desktop\Grafos\edge.csv 5453b63355474a3362317270 5453b63355474a3362317272 1

Boa. Já consegui rodar aqui. Vou extrair apenas o Dijskstra e debugar pra ver o que está acontecendo!

Olá Aderbal,

continuando com o seu Dijkstra, vou dar mais algumas dicas que facilitam o teste de algoritmos mais complexos:

• É sempre bom ter um conjunto de testes bem simples, pra gente poder acompanhar o que está acontecendo sem se perder na entrada
• É importante também isolar apenas a parte que está dando errado pra gente precisar ler menos código pra conseguir achar o bug.

Eu forkei seu repositório e fiz algumas alterações, entre elas uma entrada mais simples (que você pode visualizar no GUI e alterar pra poder testar facilmente) e removi algumas das partes que envolvem o Yen, pra gente focar no Dijkstra.

Fazendo isso, eu percebi que o Dijkstra é rodado duas vezes no CLI.java: uma dentro do g.Yen(start, end, kYen); e outra em arestas = g.Djikstra(start, end); Além disso, se eu tiro uma delas, o algoritmo quebra. Acho que aqui é um bom lugar pra começar a buscar o bug.

Dá uma fuçada aí e me diz o que você acha!

Olá Alessandro, acabei de voltar de viagem e estou dando uma olhada agora mesmo no fork que você fez

Eu dei uma olhada nas suas dicas Alessandro,

Como o arquivo é um arquivo com coordenadas reais, realmente existe a necessidade de saber se um caminho entre dois vértices é twoway ou oneway...

eu estou focando apenas no djikstra no momento, meio que "copiei" seu fork dentro do meu algoritmo e retirei o

unv = Unvisited.toArray(unv);

do for da classe Grafo.java, mas deu Null Pointer, eu pessoalmente acho que fiz cagada nessa parte de

 for (DijkstraVertice v : unv) {
                        if (v.equals(a.getFim()) || (a.isTwo_way() && v.equals(a.getInicio()))) {
                            if (v.setMinPeso(a.getPeso())) {
                                Unvisited.remove(v);
                                Unvisited.add(v);

da linha 68 da classe Grafo.Djikstra, pois o problema no momento não é o tempo de execução, e sim que ele está mostrando caminhos demais, um caminho que deveria ter tamanho 190 está tenho tamanho 7800

vou continuar fuçando aqui e te respondo a medida do possível, desculpe pela demora, hehe

Relaxa, um Dijkstra é algo bem complexo, leva um tempo pra organizar as coisas :)