SortedSet.Remove() ничего не удаляет

Question

Я в настоящее время реализую алгоритм Дейкстры, и я использую C# SortedSet в качестве очереди приоритетов. Однако, чтобы отслеживать, какие вершины я уже посетил, я хочу удалить первый элемент из очереди приоритетов.

Вот мой код:

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; 
    } 

И это компаратор:

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; 
    } 
} 

Моя приоритетная очередь не явно удерживать вершины, а у меня есть массив вершин и очереди приоритета выполняется индексы. Итак, очередь приоритетов сортируется на основе целого числа «оценка», которое имеет каждая вершина.

Теперь моя проблема заключается в том, что я могу легко получить первый элемент из SortedSet с использованием .First() или .Min, но когда я пытаюсь удалить этот элемент с помощью .Remove(), метод возвращает false, и ничего удаляется. SortedSet остается неизменным.

Любые идеи о том, как исправить это?

Заранее благодарен!

EDIT Я изменил Comparer к этому:

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; 
    } 
} 

Но теперь приоритетная очередь не содержит все необходимые элементы больше. (Обратите внимание, что очередь приоритет будет содержать указатели на вершины, которые имеют такое же значение, оценка)

Answer 1

Ваша функция сравнения никогда не сравнивает два элемента, как равно (return 0;).

Ваша коллекция не сможет удалить элемент, который не равен ни одному элементу, который он удерживает.

Пример:

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 правильно, конечно, в то время как выше версия работает, это совершенно разбитый. Лучше Comparer может быть:

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; 
    } 
}