現在、Dijkstraのアルゴリズムを実装しており、C#SortedSetを優先キューとして使用しています。 しかし、私がすでに訪れた頂点を追跡するために、私は優先順位キューから最初の項目を削除します。ここでSortedSet.Remove()で何も削除されない
は私のコードです:
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 は、私はこれに比較子を変更しました。 (プライオリティキューは、同じ推定値を持つ頂点へのポインタが含まれます、注意してください)
あなたの即時の質問に回答してきたが、私はそれは彼らがあなたの 'SortedSet'に追加されてきた後、あなたが頂点の推定値を変更するように見えることを指摘することは重要だと思います。それはうまくいかないでしょう。 'SortedSet'はアイテムを再ソートしませんし、アイテムがソートされなくなった場合はひどく壊れます。 – hvd
新しい頂点が見つかるたびに、それらをすべて事前に追加するのではなく、SortedSetに追加するようにコードを変更しました。 –