ダイクストラ法
w {\displaystyle w} を v {\displaystyle v} の「直前の頂点」と呼ぶことにする。 以下簡単のため、直前の頂点は1つしかないと仮定して話を進めるが、 一般の場合も同様である。
ダイクストラのアルゴリズムは、上述の解法をコンピュータ上でシミュレートしたものである。 グラフ G = ( V , E ) {\displaystyle G=(V,E)} 、スタートとなる頂点 s {\displaystyle s} 、および各辺 e {\displaystyle e} の長さ length ( e ) {\displaystyle {\text{length}}(e)} が入力として与えられると、 このアルゴリズムは上述の解法をシミュレートし、「落下」が停止した頂点から順に、その頂点の直前の頂点が何であるかを出力する。 ゴールとなる頂点の「落下」が停止したところで、ダイクストラのアルゴリズムを止めれば、 あとはゴールから順に、直前の頂点、さらにその直前の頂点とたどっていくことで、 ゴールとスタートをつなぐ最短経路(の一つ)を求めることができる。