ダイクストラのアルゴリズムは、開始点からの距離によって順序付けられる優先キューを使用しますが、頂点の距離はアルゴリズム中に変化します。プライオリティ キュー自体がいつ並べ替えられるかはわかりませんが、次のコンパレータがある場合:
struct compareByDistance
{
bool operator()(Vertex const &a, Vertex const &b)
{
return( getDistance(a) < getDistance(b) );
}
};
アルゴリズムの間、キューから値を削除するだけなので、それ自体が完全に並べ替えられるとは想像できません。したがって、距離の値が変更された場合、キューは距離の順序にはなりません。
これと同様にどのように実装しますか?