ダイクストラ法
話を簡単にするため、 G = ( V , E ) {\displaystyle G=(V,E)} の各頂点 v , w ∈ V {\displaystyle v,w\in V} に対し、 v {\displaystyle v} と w {\displaystyle w} を結ぶ辺は最大一つしかないとする。 v {\displaystyle v} と w {\displaystyle w} を結ぶ辺があれば、その辺を ( v , w ) {\displaystyle (v,w)} と書く。
最短経路問題は、ビー玉と紐を用いて解くことができる。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。
落下が止まった頂点 v {\displaystyle v} に対し、 v {\displaystyle v} を支えている頂点 w {\displaystyle w} が存在する。