1

Estou tentando aplicar o algoritmo de Dijkstra usando Priority queue

  • Preciso deixa-lo com complexidade logaritmica T(N) = E*log(n)
  • O primeiro nó consegue achar seus vizinhos e relaxar seus valores mas a segunda iteração está errada. Parece ser um problema com o comparator e o pull da priority queue

Acho que estou fazendo algo errado, pois eu retorno o nextNode (n2, que seria o proximo nó a ser visitado depois do primeiro) mas depois de fazer o poll ele acaba considerando o n5 como a cabeça)

O que estou fazendo de errado? Preciso de ajuda :(

Se alguém também souber o que preciso mudar para deixa-lo com complexidade logaritmica, ajudaria muito

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;

import java.util.PriorityQueue;
//import java.util.Queue;

public class Main {
    
    public static int infinity = (Integer.MAX_VALUE)/2; 
    
    public static Node RelaxingNodes(Node currentNode) {        
        System.out.println("Nó atual:");
        System.out.println(currentNode.getLabel());
        
        Node nextNode = null;
        int minDistance = infinity;
        
        // Relaxa os vizinhos e seleciona o mais perto
        Map<Node, Integer> edges = currentNode.getNeighbourerList();
        
        for (Map.Entry<Node, Integer> e : edges.entrySet()) {
            Node neighbor = e.getKey();
            int neighbor_distancia = e.getValue();
            
            System.out.println("Vizinho:");
            System.out.println(neighbor.getLabel());  // Node v
            System.out.println("Aresta até o vizinho:");
            System.out.println(neighbor_distancia); // Distance value
            
            int newDistance = currentNode.getDistanceFromS() + neighbor_distancia;
            int currentDistance = neighbor.getDistanceFromS();
            System.out.println("Distancia atual");
            System.out.println(currentDistance);
            if (newDistance < currentDistance) {
                neighbor.setDistanceFromS(newDistance);
            }
            System.out.println("Nova Distancia");
            System.out.println(neighbor.getDistanceFromS());
            
            if (newDistance < minDistance) {
                nextNode = neighbor;
                System.out.println("Proximo vizinho");
                System.out.println(nextNode.getLabel());
            }
        }
                
        return nextNode;
    }
    
    
    public static void main (final String[] args) {
        
             
        // Cria os nós
        
        // d[v] = infinito estimativa de distancia de s (vertice inicial) a todos os vertices = infinito
        // d[s] = 0
        // p[v] = -1 precededentes inicialmente sao -1, pois ainda nao sabemos 
        
                      //nome, p[v], d[v] 
        Node s = new Node("v0", 0, -1, 0);
        Node n1 = new Node("v1", 0, -1, infinity);
        Node n2 = new Node("v2", 0, -1, infinity);
        Node n3 = new Node("v3", 0, -1, infinity);
        Node n4 = new Node("v4", 0, -1, infinity);
        Node n5 = new Node("v5", 0, -1, infinity);
        
        Node from = s;
        Node to = n5;
        
        s.addNeighbor(n1, 10);
        s.addNeighbor(n2, 5);
        n1.addNeighbor(n3, 1);
        n2.addNeighbor(n1, 3);
        n2.addNeighbor(n3, 8);
        n2.addNeighbor(n4, 2);
        n3.addNeighbor(n5, 4);
        n3.addNeighbor(n4, 4);
        n4.addNeighbor(n5, 6);
        
        // escolha o vertice aberto u cuja estimativa seja a menor possivel (inicialmente s, 0)
        // feche u
        // para todo nó aberto vizinho dele,  atualize as estimativas de distancia
        // relaxamento:
            // some d[u] ao peso da aresta (u,v)
            // caso a soma seja menor que d[v], atualize d[v] e faça p[v] = u
        
        // começando em 0: a distancia do s [-1, 0] + valor_aresta é menor que a distancia do no v [-1, infinito]
        // sim, entao substitue, se nao, ignora
        // va pro proximo no com menor estimativa vizinho de s
          
        
        // aberto[v] = true: todos os vertices = abertos
//        boolean[] visited = new boolean[n];
        
        // Vizinhos de um No 
        PriorityQueue<Node> nodeToVisit = new PriorityQueue<>(
                new Comparator<Node>() {
                    @Override
                    public int compare(Node a, Node b) {
                        return Integer.valueOf(a.getValue()).compareTo(b.getValue());
                    }
                }
                ); 
       
        nodeToVisit.add(s);
        nodeToVisit.add(n1);
        nodeToVisit.add(n2);
        nodeToVisit.add(n3);
        nodeToVisit.add(n4);
        nodeToVisit.add(n5);
        
        
        Node currentNode = s;
        Node nextNode = null;
        
        // Enquanto estiverem nós abertos     
        while (!nodeToVisit.isEmpty()) {
                
            System.out.println("****** ITERACAO ***********");
            
            System.out.println("a");
            System.out.println(currentNode.getLabel());
            
                currentNode = nodeToVisit.poll(); // fecha (remove da lista de abertos)
                
            System.out.println("b");
            System.out.println(currentNode.getLabel());
            
            nextNode = RelaxingNodes(currentNode);
                
            System.out.println("c");
            System.out.println(currentNode.getLabel());
            
            System.out.println("d");
            System.out.println(nextNode.getLabel());
                
//              currentNode = nextNode; 

                
            System.out.println("e");
            System.out.println(currentNode.getLabel());
            
            System.out.println("f");
            System.out.println(nextNode.getLabel());
        }    

    }  

}

Saida:

****** ITERACAO ***********
a
v0
b
v0
Nó atual:
v0
Vizinho:
v1
Aresta até o vizinho:
10
Distancia atual
1073741823
Nova Distancia
10
Proximo vizinho
v1
Vizinho:
v2
Aresta até o vizinho:
5
Distancia atual
1073741823
Nova Distancia
5
Proximo vizinho
v2
c
v0
d
v2
e
v0
f
v2

****** ITERACAO ***********
a
v0
b
v5 *<<<<<<<<<<<<<<< PROBLEMA*
Nó atual:
v5
c
v5
d

0

Você deve fazer log-in para responder a esta pergunta.

Pesquise outras perguntas com a tag .