Решение задачи о минимаксном пути с некоторыми ограничениями

Question

У меня проблема, когда дан ненаправленный граф с положительными весами.Есть N вершин, и мне нужно получить минимальный максимальный вес между 2 вершинами в пути из всех возможных путей от вершины 1 до N. Однако общий вес этих возможных путей не может быть больше чем T.

Я понял, что это проблема минимаксного пути, поэтому я мог построить минимальное остовное дерево из графа, и оттуда я мог бы получить минимальный максимальный вес путей.Но как я могу построить минимальное остовное дерево с тем условием, что общий вес от 1 до N не может быть больше чем T?

Например.На рисунке только 1256 и 1356 являются возможными путями, если T равно 13. Путь 1456 не учитывается, поскольку общий вес составляет 14.

А между 1256 и 1356 край 35 веса 7 являетсяминимаксная масса дорожек.

Answer 1

Предполагая, что веса положительных фронтов можно решить за O ((m + n log n) log m), выполнив бинарный поиск, по которому из m ребер есть минимальный максимум.Бинарный поиск требует O (log m) итераций, каждая из которых стоит O (m + n log n) времени с алгоритмом Дейкстры, чтобы найти кратчайшие пути на графе со всеми ребрами, которые весят не больше максимума, проверяя, есть лидостаточно короткий путь от 1 до N.