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

私のプライオリティキューは、明示的に、私は頂点の配列を持っており、プライオリティキューが保持している代わりに、頂点を保持していませんインデックス。 したがって、優先度キューは、各頂点が保持する「推定」整数に基づいてソートされます。

今、私の問題は、.First（）または.Minを使用してSortedSetから最初の要素を簡単に取得できますが、その要素を.Remove（）で削除しようとすると、削除されます。 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; 
    } 
} 

しかし、今のプライオリティキューはもうすべての権利の要素が含まれていません：

EDIT は、私はこれに比較子を変更しました。 （プライオリティキューは、同じ推定値を持つ頂点へのポインタが含まれます、注意してください）

Answer 1

あなたの比較関数決しては等しいなどの2つの要素（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; 
    } 
}