グラフの一種である木構造での距離を求めるアルゴリズムを考えます.
グラフとは
詳しくは グラフ理論 - Wikipedia などの記述をご参照ください.
グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを表しているものです(頂点の集合は自然数の部分集合と同型なので, それぞれの頂点には何番目の頂点かを表す自然数が割り当てられます. 一般には辺それぞれには実数の重みがあり, その頂点同士の移動にかかるコストを表しています. 辺は の形式を持ち, 頂点 から頂点 はコスト で隣接していることを表しています. 重み付きでない場合は, と理解します.
辺に向きがあるもの(つまり, 2つの頂点について行けるのに戻れなかったりコストが等しくなかったりするもの)を有向グラフ(directed graph), 辺に向きがないもの(つまり, 頂点間のコストは行きと帰りで等しいもの)を無向グラフ(undirected graph)といいます. 無向グラフでは なる辺があったとき, 逆向きの を辺にもつ有向グラフと解釈することもできます.