想象一下，给定一个加权无向完全图，其中 n 个节点具有非负权重 Cij，其中 i = j Cii = 0，并且 i != j Cij > 0。假设你必须找到任意两个节点之间的最大最短路径节点 i 和 j。在这里，您可以轻松地使用 Floyd-Warshall，或使用 Dijkstra n 次，或其他任何方法，然后在所有 n^2 最短路径中找到最大值。
现在假设 Cij 不是常数，而是可以取两个值，Aij 和 Bij，其中 0 <= Aij <= Bij。我们也有 Aii = Bii = 0。假设您还需要找到最大最短路径，但约束条件是 m 边必须取值 Bij 和其他 Aij。并且，如果 m > n^2，则所有边都等于 Bij。但是，当找到最短路径 i -> p1 -> ... -> pk -> j 时，您对最坏的情况感兴趣，因为在该路径上您需要选择那些边来获取 Bij 的值，例如如果您在其方向上有固定节点，则该路径值最大。
例如，如果您有长度为 4 iklj 的路径，并且在该路径上的最优解中，只有一个权重更改为 Bij，而其他取 Aij 的值。并设 m1 = Bik + Akl + Alj，m2 = Aik + Bkl + Alj，m3 = Aik + Akl + Blj，该路径的值为 max{m1, m2, m3}。因此，在 i 和 j 之间的所有路径中，您必须选择一个使得最大值（如本例中所述）最小的（这是最短路径定义的一种变体）。你必须对所有对 i 和 j 都这样做。
您没有得到约束，您需要在每条路径上改变多少，而是给出 m 的值，即在完整图中应该变化的权重的数量。问题是找到最短路径的最大值，如前所述。
另外，我的问题是：这是 NP 难题，还是存在一些多项式解决方案？