ダイクストラ法
「 u ← d ( u ) {\displaystyle u\leftarrow d(u)} が最小である頂点 u ∈ Q {\displaystyle u\in Q} 」:二分ヒープもフィボナッチヒープも O ( V ) {\displaystyle O(V)}
「 Q {\displaystyle Q} から u {\displaystyle u} を取り除き取り出す」:二分ヒープもフィボナッチヒープも O ( V log  V ) {\displaystyle O(V\log V)}
「 d ( v ) ← d ( u ) + length ( u , v ) {\displaystyle d(v)\leftarrow d(u)+{\text{length}}(u,v)} 」:二分ヒープは O ( E log  V ) {\displaystyle O(E\log V)} 、フィボナッチヒープは O ( E ) {\displaystyle O(E)}
以上の考察から分かるように、ダイクストラ法では「次に落下が停止する頂点」(とその直前の頂点)を求めることが重要である。 そこでこれらを効率的に求める方法を説明する。
現時点で「落下」が停止している頂点の集合をHとし、 各頂点 v ∈ V {\displaystyle v\in V} に対して H ∪ v {\displaystyle H\cup {v}} 内での v {\displaystyle v} と s {\displaystyle s} との最短距離を d ( v ) {\displaystyle d(v)} とする( H ∪ v {\displaystyle H\cup {v}} 内で s {\displaystyle s} から v {\displaystyle v} に到達できないときは d ( v ) = inf {\displaystyle d(v)=\inf } とする)。 さらに、 H {\displaystyle H} に隣接している頂点の集合を A {\displaystyle A} とする。 ここで頂点 v {\displaystyle v} が H {\displaystyle H} に隣接しているとは、 v {\displaystyle v} と H {\displaystyle H} 内のいずれか頂点を結ぶ辺が存在することを指す。