歩道・道・距離

グラフ $G=(V,E)$ において、頂点の列 $W=(v_0,v_1,\ldots,v_k)$ が、すべての $i$ について $v_i$ と $v_{i+1}$ が辺で結ばれている（有向グラフなら $(v_i,v_{i+1}) \in E$）とき、$W$ を $v_0$ から $v_k$ への歩道といい、$k$ をその長さという。

歩道 $W$ の頂点がすべて相異なるとき、$W$ を道という。$k \ge 1$ で、$v_0=v_k$ かつ $v_0,\ldots,v_{k-1}$ が相異なるとき、$W$ を閉路という。ただし無向グラフでは、同じ辺を往復するだけの $k=2$ の場合を除くため $k\ge3$ を要求する。

$s$ から $v$ への歩道が存在するとき、$v$ は $s$ から到達可能であるという。$s$ から $v$ への歩道の長さの最小値を $\delta(s,v)$ と書き、$s$ から $v$ への距離という。到達可能でないときは $\delta(s,v)=\infty$ と定める。