辺に向きのないグラフで、辺の重み(距離)が S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−T: 3、A−T: 6 である。ダイクストラ法で S から T までの最短経路を求めたとき、その経路と長さはどれか。

正解：B. S→B→A→C→T、長さ7

ダイクストラ法は、距離が確定していない頂点のうち最も近いものを確定し、その隣の頂点の距離を更新することを繰り返します。S(0)から B が1で確定し、B を通ると A は 1 + 2 = 3 で直接の4より短くなります。A(3)を確定すると C は 3 + 1 = 4、T は 3 + 6 = 9 になり、C(4)を確定すると T は 4 + 3 = 7 に更新されます。したがって最短経路は S→B→A→C→T で長さは7です。S→A→C→T(8)は S−A を直接通る分だけ長く、S→B→C→T(9)は B−C の5が大きいため長くなります。

• A. S から A へは、直接(4)より B を通る方(1 + 2 = 3)が短くなります。
• B. 正しい。S→B(1)、B→A(2)、A→C(1)、C→T(3)で合計7です。
• C. B−C の重み5が大きく、A を通る方が短くなります。