これは古い中間試験の問題の例です。
G = (V, E) を連結無向グラフとし、辺には正の整数の辺の重みが関連付けられており、頂点 s ∈ V がソースです。各頂点 t ∈ V について、s から t への非減少パス (そのようなパスがない場合は ∞) の最小の最後のエッジの重みを報告するアルゴリズムを提供します。パス v1、v2、. . . i = 1, 2, ...r−2 に対して w(v_i, v_i+1) ≤ w(v_i+1, v_i+2) の場合、vr は非減少です。
問題は、開始頂点を持つグラフが与えられ、最短パスの長さを見つけることができ、パスを下るにつれてエッジの重みが増加するアルゴリズムを考え出すことを問題が望んでいると考えて正しいですか?到達できる頂点？