SortedSet.Remove() 不删除任何内容

Question

我目前正在实施 Dijkstra 算法，并且我正在使用 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;
    }
}

我的优先队列没有明确保存顶点，而是我有一个顶点数组，优先队列保存索引。所以优先级队列是根据每个顶点持有的 'estimate' 整数排序的。

现在我的问题是，我可以使用 .First() 或 .Min 轻松地从 SortedSet 中检索第一个元素，但是当我尝试使用 .Remove() 删除该元素时，方法 returns false，什么都不会被删除。 SortedSet 保持不变。

关于如何解决这个问题有什么想法吗？

提前致谢！

编辑我将比较器更改为：

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

您的比较函数 never 将两个元素比较为 equal (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 当然是正确的，虽然上面的版本有效，但它很破。更好的比较器可能是：

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

SortedSet.Remove() 不删除任何内容

SortedSet.Remove() does not remove anything

c#

graph

dijkstra

sortedset