Shortest Reach in a Graph in Hacker Rank
問題
n個のノードとm個のエッジによって構成されるグラフが与えられ、スタートノードからその他の全てノードまでの最短距離を求める問題。
解法
優先度付きキューを用いたダイクストラ法を使って解く
計算量
優先度付きキューに値を追加する操作と取り出す操作はO(logN)で行えるの。
グラフにおけるノードの数をV、エッジの数をEとすると優先度付きキューを用いたダイクストラ法の計算量はO((V + E)logV)となる。今回、2 ≦ V ≦ 10^3, 1 ≦ E ≦ V(V-2)/2なので**O(106log103)となる。また、この処理をクエリーの数q(1 ≦ q ≦ 10)だけ行うので最終的な計算量はO(107log103)となる。
クラスのプロパティによってオブジェクトをソートする
今回優先度付きキューに入れるのは自作したクラスのオブジェクトだ。オブジェクトの持つdistanceプロパティの値によってソートさせたい。こういう時は自作したクラスに対してimplements ComparableとしてcompareToメソッドを実装することで実現できる。
