最長最短経路（あまり）

Question

私の学士論文では、次の問題が発生しました（実際の問​​題の解決に役立つ可能性があります）。頂点がVであり、Vから2つの頂点、開始s、および宛先tの加重有向グラフGがあります。ほとんどのkの頂点を削除できます。頂点を見つけ出す必要があります。その頂点を削除すると、調整されたグラフの最短経路のコスト（長さ）がsからtに最大化されます。

私は、この問題は文献の前に取り組まれていたはずですが、関連記事を見つけることはできませんでした。私は関連文献へのリンクに感謝します。

Answer 1

Yen's Algorithmを適用して、最短のKパスを見つけることができます。今あなたのコードにそれをどのように適用しますか？最初のKパスではなく、最短と同じ長さを持つすべてのパスに対して適用します。それらのすべて（K1を数えて）を見つけたら、各パスを取って、1つの頂点を削除します（既にスキップしていると考えている場合は削除します）。そうでなければ、最短パスの問題があります。スキップ可能な頂点を持つグラフ。各ステップで、「最短経路」を最大にしようとし、その頂点を選択しました。私はより最適な方法を考えていますが、これは私の頭の上からできる最高です。私が言ったように

1. ドゥ円のアルゴリズムが変更：

   あなたはKの時間を行います。

2. 最小距離を増やすために、1つの頂点を削除する最適な局所解を求めます。