個人的備忘録
辺の数を\(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})$$
個人的備忘録
辺の数を\(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})$$