SortedSet.Remove()方法不会删除任何内容。

Question

SortedSet.Remove()方法不会删除任何内容。

6

我目前正在实现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;
    }
}

我的优先队列并没有明确地持有顶点，而是我有一个顶点数组，优先队列持有这些索引。因此，优先队列基于每个顶点所持有的“估算”整数进行排序。

现在我的问题是，我可以使用.First()或.Min轻松检索SortedSet中的第一个元素，但当我尝试使用.Remove()删除该元素时，方法返回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;
    }
}

但现在优先队列中不再包含所有正确的元素。 (请注意，优先队列将包含具有相同估计值的顶点指针)

- van Leemhuyzen

1

虽然你的问题已经得到了回答，但我认为指出一点很重要，那就是在将顶点添加到你的“SortedSet”之后，你似乎正在改变它们的估计值。这样做是行不通的。“SortedSet”不会重新排序任何项，并且如果项目不再排序，它将会出现严重错误。 - user743382

我也注意到了，我已经修改了我的代码，每当我发现一个新的顶点时，它会被添加到 SortedSet 中，而不是事先添加它们全部。 - van Leemhuyzen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nvoigt · Accepted Answer

你的比较函数永远不会将两个元素视为相等（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;
    }
}