Implémentation d'une classe de comparaison pour la file d'attente prioritaire utilisée dans l'algorithme de Dijkstra?

Question

J'essaye de mettre en application l'algorithme de Dijsktra du livre CLRS - Introduction aux algorithmes, cependant, j'ai de la difficulté à implémenter une file d'attente prioritaire avec l'interface Comparator. C'est ma classe de Vertex comme vous pouvez le voir;

public class Vertex { 

    public boolean explored; 
    public int vertexID; 
    public LinkedList<Vertex> adjacencyList; 
    public LinkedList<Edge> edgeSet; 
    public int shortestDistance; 
    public Vertex predecessor; 

    public Vertex(int vertexID){ 

     this.vertexID = vertexID; 
     this.explored = false; 
     this.adjacencyList = new LinkedList<>(); 
     this.edgeSet = new LinkedList<>(); 
     this.shortestDistance = Integer.MAX_VALUE; 
     this.predecessor = null; 
    } 
} 

donc d'abord shortestDistance attribut est déclaré Integer.MAX_VALUE. De plus, vous pouvez voir la classe qui implémente depuis Comparator, est utilisée pour la file d'attente prioritaire.

public class WeightComparator implements Comparator<Vertex> { 

    @Override 
    public int compare(Vertex o1, Vertex o2) { 

     return Math.min(o1.shortestDistance, o2.shortestDistance); 
    } 
} 

Je suis sûr que la mise en œuvre tout n'a pas d'erreurs logiques en raison de mes quelques tests, cependant, dans certains tests, il échoue. Je crée une référence à ma file d'attente avec cette déclaration

PriorityQueue<Vertex> queue = new PriorityQueue<>(N, weightComparator);

où N est la taille de la file d'attente. Alors s'il vous plaît corrigez-moi si je me trompe sur la façon dont cela fonctionne. Lorsque vous en aurez un article, il supprimera l'article qui a le moins de priorité? J'espère qu'il a été clair pour comprendre mon problème, et j'apprécierai beaucoup si quelqu'un peut aider à ce sujet. Donc, merci quand même

Answer 1

Math.min vous donne la plus petite de deux valeurs. Retourner cela comme une valeur de comparaison est faux.

Une valeur compare retour < 0 signifie que la première valeur est inférieure à la seconde, mais si vous revenez Math.Min(5, 3), vous obtiendrez 3, qui est> 0, ce qui signifie que le comparateur va lui dire que 3> 5. Ce qui est faux.

Ce que vous cherchez est:

public int compare(Vertex o1, Vertex o2) { 
    return Integer.compare(o1.shortestDistance, o2.shortestDistance); 
} 

Answer 2

À moins que shortestDistance puisse être négatif, votre comparateur ne peut jamais retourner un nombre négatif. Ce n'est donc pas une implémentation correcte.

Conceptuellement, un comparateur pour les primitives doit renvoyer une soustraction:

return o1.shortestDistance-o2.shortestDistance; 

ou l'inverse si vous voulez descendre. Mais vous devez vous méfier des problèmes de débordement.