個人的備忘録

辺の数を\(E\),頂点の数を\(V\)とする。 スタート地点とゴール地点は固定されている。

オリジナル

vectorなどの配列のみで実装した場合

$$\mathcal{O} (V^2 + E) = \mathcal{O} (VV + E)$$

優先度付き待ち行列

priority_queを使って実装した場合

$$\mathcal{O} ((V+E)\log{E}) = \mathcal{O} (V\log{E} + E\log{E})$$