頂点 S, A, B, C, T と、重み付きの無向辺 S−A(4), S−B(1), B−A(2), A−C(1), B−C(5), C−T(3), A−T(6) からなるグラフがある（括弧内は辺の重み）。ダイクストラ法で求めた S から T への最短距離はいくつか。

解説

正解は「7」です。ダイクストラ法では、距離が未確定の頂点のうち暫定距離が最小のものを確定し、そこから出る辺で隣接頂点の暫定距離を更新します。S（0）から始めて B（1）を確定すると、A が3、C が6 に更新されます。次に A（3）を確定すると、C が4、T が9 に更新されます。C（4）を確定すると T が7 に更新され、最後に T が7で確定します。経路は S→B→A→C→T です。「8」は S→A→C→T のように、直接の辺 S−A（4）を使った場合です。「9」は S→B→C→T などの場合、「10」は S→A→T の場合で、いずれも最短ではありません。