重み付けされていない無向グラフの隣接行列が与えられた場合、任意の 2 つのノード s と t の間の最短経路の長さを拡張/増加する効率的な方法 (多項式アルゴリズム) はありますか?
例：
以下の例では、頂点 s=1 から頂点 t=5 までの 5 つの異なる「最短パス」があり、それぞれの長さは 3 です。最小数のエッジを削除して、最短パスの長さが強制的に 4 またはもっと。(グラフの切断は問題ありません。)
隣接行列 (例を修正するために拡張):
0 1 0 0 0 1 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 1
0 1 0 0 1 1 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0
1 0 0 1 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1 0 0 0
1 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
このグラフを表す:
最短経路長を強制的に 3 から 4 に増加させるための最小コストは、2 つのエッジ (1,2) と (5,9) を削除することです。
ゴール：
一般的なケースで削除する必要があるエッジのセットを見つける一般的なアルゴリズムについて何かアイデアをいただけますか?
訂正:私のコメントで述べたように、この例は完全ではありません。さらに 2 つの頂点 10 と 11 (赤で表示) を追加することで、この例は救われます。