ダイクストラ法
「 u ← Q {\displaystyle u\leftarrow Q} から d ( u ) {\displaystyle d(u)} が最小である頂点を取り除き取り出す」の部分は、エドガー・ダイクストラによるオリジナルでは単純に集合内を探索するアルゴリズムだが、その操作の計算量を減らすために、 Q {\displaystyle Q} として、優先度付きキュー(フィボナッチヒープ)を用いることが行われる。ただしその場合、 Q {\displaystyle Q} に関する部分を少し変更する必要がある。下記は優先度付きキューを用いたことを想定し上記を書き換えたダイクストラ法の擬似コードである。
「for each ( u {\displaystyle u} からの辺がある各頂点 v ∈ V {\displaystyle v\in V} )」の部分は「for each ( u {\displaystyle u} からの辺がある各頂点 v ∈ Q {\displaystyle v\in Q} )」でも同じ結果が得られるが、 Q ⊂ V {\displaystyle Q\subset V} ではあるものの、逆に計算量が増えてしまう場合もあり得ることに注意。
GCC の C++ の priority_queue はペアリングヒープを使用しているため、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。
(a)の長さは u {\displaystyle u} を H {\displaystyle H} に追加する前の段階での d ( v ) {\displaystyle d(v)} に一致し、 一方(b)の長さは u {\displaystyle u} を H {\displaystyle H} に追加する前の段階での d ( u ) {\displaystyle d(u)} に length ( u , v ) {\displaystyle {\text{length}}(u,v)} を加えた長さである。
以上の考察より、 d ( v ) {\displaystyle d(v)} および w v {\displaystyle w_{v}} を次のように更新すればよいことがわかる:
u {\displaystyle u} から v {\displaystyle v} への辺が存在する各 v {\displaystyle v} に対し、 d ( v ) > d ( u ) + length ( u , v ) {\displaystyle d(v)>d(u)+{\text{length}}(u,v)} なら、 d ( v ) {\displaystyle d(v)} を「 d ( u ) + length ( u , v ) {\displaystyle d(u)+{\text{length}}(u,v)} 」に更新し、さらに w v {\displaystyle w_{v}} を u {\displaystyle u} に更新。 そうでなければ何もしない。