SortedSet.Remove() entfernt nichts

Question

Ich implementiere derzeit den Dijkstra-Algorithmus und verwende C# SortedSet als Prioritätswarteschlange. Um jedoch zu verfolgen, welche Scheitelpunkte ich bereits besucht habe, möchte ich das erste Element aus der Prioritätswarteschlange entfernen.

Hier ist mein Code:

static int shortestPath(int start, int target) 
    { 
     SortedSet<int> PQ = new SortedSet<int>(new compareByVertEstimate()); 
     for (int i = 0; i < n; i++) 
     { 
      if (i == start - 1) 
       vertices[i].estimate = 0; 
      else 
       vertices[i].estimate = int.MaxValue; 

      PQ.Add(i); 
     } 

     int noOfVisited = 0; 
     while (noOfVisited < n) 
     { 
      int u = PQ.First(); 
      noOfVisited++; 

      foreach (Edge e in vertices[u].neighbours) 
      { 
       if (vertices[e.target.Item1].estimate > vertices[u].estimate + e.length) 
       { 
        vertices[e.target.Item1].estimate = vertices[u].estimate + e.length; 
       } 
      } 

      PQ.Remove(u); 
     } 
     return vertices[target - 1].estimate; 
    } 

Und das ist der Vergleich:

public class compareByVertEstimate : IComparer<int> 
{ 
    public int Compare(int a, int b) 
    { 

     if (Program.vertices[a].estimate >= Program.vertices[b].estimate) return 1; 
     else return -1; 
    } 
} 

Meine Prioritätswarteschlangen Eckpunkte nicht explizit halten, sondern habe ich eine Reihe von Eckpunkten und die Prioritätswarteschlange halten die Indizes. Die Prioritätswarteschlange wird also basierend auf der "Schätzung" -Ganzzahl sortiert, die jeder Scheitelpunkt enthält.

Jetzt ist mein Problem, ich kann das erste Element aus dem SortedSet mit .First() oder .Min leicht abrufen, aber wenn ich versuche, dieses Element mit .Remove() zu entfernen, gibt die Methode false und nichts zurück wird entfernt. Das SortedSet bleibt unverändert.

Irgendwelche Ideen, wie Sie das beheben können?

Vielen Dank im Voraus!

EDIT änderte ich den Comparer dazu:

public class compareByVertEstimate : IComparer<int> 
{ 
    public int Compare(int a, int b) 
    { 

     if (Program.vertices[a].estimate == Program.vertices[b].estimate) return 0; 
     else if (Program.vertices[a].estimate >= Program.vertices[b].estimate) return 1; 
     else return -1; 
    } 
} 

Aber jetzt ist die Prioritätswarteschlange nicht die richtigen Elemente alle mehr enthält. (beachten Sie, dass die Prioritäts-Warteschlange Zeiger auf Vertices enthält, die den gleichen Schätzwert haben)

Answer 1

Ihre Vergleichsfunktion nie vergleicht zwei Elemente als gleich (return 0;).

Ihre Sammlung wird nicht in der Lage sein, ein Element zu entfernen, das keinem der Elemente entspricht, die es enthält.

Beispiel:

public class compareByVertEstimate : IComparer<int> 
{ 
    public int Compare(int a, int b) 
    { 

     if (a == b) return 0; 

     if (Program.vertices[a].estimate >= Program.vertices[b].estimate) return 1; 

     return -1; 
    } 
} 

@hvd ist natürlich richtig, während die obige Version funktioniert, es ist ziemlich kaputt. Ein besserer Vergleich könnte sein:

public class compareByVertEstimate : IComparer<int> 
{ 
    public int Compare(int a, int b) 
    { 
     var ae = Program.vertices[a].estimate; 
     var be = Program.vertices[b].estimate; 

     var result = ae.CompareTo(be); 

     if (result == 0) return a.CompareTo(b); 

     return result; 
    } 
}