頂点間の距離 - Boost Graph の使い方

頂点間の距離

グラフにおいて、ある頂点同士の最短パスの事を頂点間の距離と言います。

上記グラフにおいて、頂点 v1 と v5 のパスは複数存在します。
p1 = { v1, v2, v3, v4, v5 }
p2 = { v1, v2, v4, v5 }
p3 = { v1, v3, v5 }
この場合 p3 のパスが頂点 v1 と v5 の距離という事になります。

２頂点間の距離を d( u, v ) と記述します。
上記例だと d( v1,v5 ) = 2 となります。

なお、頂点間のパスが存在しない場合の距離は無限大となります。