i = j Cii = 0 および i != j Cij > 0 である非負の重み Cij を持つ n 個のノードを持つ重み付き無向完全グラフが与えられたとします。任意の 2 つの間の最大最短経路を見つける必要があるとします。ノード i と j。ここでは、Floyd-Warshall を簡単に使用したり、Dijkstra を n 回使用したりして、n^2 のすべての最短経路の中で最大のものを見つけることができます。
ここで、Cij は定数ではなく、0 <= Aij <= Bij である Aij と Bij の 2 つの値を取ることができると仮定します。また、Aii = Bii = 0 もあります。最大最短経路も見つける必要があると仮定しますが、m 個のエッジが値 Bij を取り、その他の Aij を取らなければならないという制約があります。また、m > n^2 の場合、すべてのエッジは Bij に等しくなります。しかし、最短パス i -> p1 -> ... -> pk -> j を見つけるとき、そのパスで Bij の値を取るためにそれらのエッジを選択する必要があるという意味で、最悪の場合に興味があります。その方向に固定ノードがある場合、そのパス値は最大になります。
たとえば、長さ 4 iklj のパスがあり、そのパスの最適解では、1 つの重みだけが Bij に変更され、他の重みは Aij の値を取る場合。そして、m1 = Bik + Akl + Alj、m2 = Aik + Bkl + Alj、m3 = Aik + Akl + Blj とすると、そのパスの値は max{m1, m2, m3} です。したがって、i と j の間のすべてのパスの中で、最大値 (この例で説明) が最小になるようなパスを選択する必要があります (これは、最短パスの定義の変形です)。そして、すべてのペア i と j に対してそれを行う必要があります。
各パスでいくつ変更する必要があるかという制約は与えられませんが、完全なグラフで変更する必要がある重みの数である m の値が与えられます。そして問題は、説明したように、最短経路の最大値を見つけることです。
また、私の質問は次のとおりです。これはNP困難な問題ですか、それとも多項式の解が存在しますか?