問題は次のとおりです。5 つの頂点を持つ有向グラフを考えてみましょう。図 1 に示すように、ダイクストラのアルゴリズムがノード s から他のすべてのノードへの最短経路を生成するとします。エッジ (x, t) の重みを増やし、すべてのノードが何らかの方法でこの情報を取得すると仮定します。ノード s はダイクストラのアルゴリズムをどのように変更して再計算を最小限に抑えますか? 「ノード s は、S を として初期化し、リスト (< 各ノード >) を として維持することにより、ダイクストラのアルゴリズムを実行する」という形式で最終的なソリューションを提供します。</p>
私の質問は... s から t への最短経路を増やすだけなので、それはひっかけ問題ではありませんか?
よし、私の写真は機能していない
しかし、それは次のように機能します：
s->y->x->t
y は z も指します。y->z
これらは一方向矢印です。