SortedSet.Remove() does not remove anything

Question

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.

Here is my 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;
    }

And this is the comparer:

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

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.

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.

Any ideas on how to fix this?

Thanks in advance!

EDIT I changed the Comparer to this:

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

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)

Answer 1

Your compare function never compares two elements as equal (return 0;).

Your collection will not be able to remove an element that is not equal to any element it holds.

Example:

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 is correct of course, while the above version works, it's quite broken. A better comparer might be:

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