用一些约束解决minimax路径问题

Question

我有一个问题，其中给出了具有正权重的无向图。有N个顶点，我需要获得从vetex 1到N的所有可能路径的路径中2个顶点之间的最大权重。但是这些可能路径的总权重不能超过T.

我意识到这是一个minimax路径问题，所以我可以从图形构建一个最小生成树，从那里，我可以得到路径的最小 - 最大权重。但是如何构造最小生成树的约束条件是从1到N的总权重不能超过T？

例如。在图片中，如果T为13，则只有1256和1356是可能的路径。不考虑路径1456，因为总重量加起来为14。

并且在1256和1356之间，重物7的边缘35是路径的最小重量。

Answer 1

假设正边缘权重，您可以通过二进制搜索在m（（m + n log n）log m）时间内解决此问题，其中m个边缘中的哪一个是最小最大值。二进制搜索需要O（log m）次迭代，每次迭代都需要用Dijkstra算法计算O（m + n log n）时间才能找到图中的最短路径，所有边缘的权重不超过最大值，测试是否存在足够短的路径从1到N.