SortedSet.Remove() does not remove anything
<p>I am currently implementing Dijkstra's algorithm and I am using the C# SortedSet as a priority queue.
However, in order to keep track of what vertices I have already visited, I want to remove the first item from the priority queue.</p>

<p>Here is my code: </p>

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

            PQ.Add(i);
        }

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

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

            PQ.Remove(u);
        }
        return vertices[target - 1].estimate;
    }
</code></pre>

<p>And this is the comparer:</p>

<pre><code>public class compareByVertEstimate : IComparer&lt;int&gt;
{
    public int Compare(int a, int b)
    {

        if (Program.vertices[a].estimate &gt;= Program.vertices[b].estimate) return 1;
        else return -1;
    }
}
</code></pre>

<p>My priority queue does not explicitly hold vertices, instead I have an array of vertices and the priority queue holds the indices.
So the priority queue is sorted based on the 'estimate' integer that each vertex holds. </p>

<p>Now my problem is, I can easily retrieve the first element from the SortedSet using .First(), or .Min, but when I try to remove that element with .Remove(), the method returns false, and nothing gets removed. The SortedSet remains unchanged.</p>

<p>Any ideas on how to fix this?</p>

<p>Thanks in advance!</p>

<p><strong>EDIT</strong>
I changed the Comparer to this:</p>

<pre><code>public class compareByVertEstimate : IComparer&lt;int&gt;
{
    public int Compare(int a, int b)
    {

        if (Program.vertices[a].estimate == Program.vertices[b].estimate) return 0;
        else if (Program.vertices[a].estimate &gt;= Program.vertices[b].estimate) return 1;
        else return -1;
    }
}
</code></pre>

<p>But now the priority queue doesn't contain all the right elements anymore.
(Note, the priority queue will contain pointers to vertices that have the same estimate value)</p>