頂点を都市として、エッジを都市間の距離として持つグラフが与えられます。それぞれの都市には、それに関連付けられた特定の数の休日があります。最初に、出発点が与えられます。ここでの目標は、距離を最小限に抑えながら、できるだけ多くの休日を収集する必要があるように、グラフ内のパスを見つけることです。
例: グラフを考えてみましょう: 頂点の重み:
(City -> Holidays)
A -> 30
B -> 35
C -> 45
エッジの重み
A -> B (Distance is 2)
A -> C (Distance is 8)
A から開始した場合、収集できる最大の休日は、パス A -> B で距離が「2」の 65 です。パス A -> C は選択しませんが、距離が「8」であるため、休日は 75 になります。