Maximum Capacity Path Problem with constraints

Question

I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output. The problem is:
Given an undirected graph with two parameters (weight,cost). We need to find the Maximum Capacity path problem from source to destination such that the cost of the path(sum of the edges of path) is within a fixed value specified by the user. In other words, it(sum of cost parameter along the path) is upper bounded by a constant value.
I modified the existing algorithm by adding and extra cost constraint while relaxing the edges but was unable to make it work for all types of graph. I was also wondering if this problem is NP-Complete.

Answer 1

It can be solved in polynomial time. For instance, you can use binary search over the weight. Given a candidate weight, delete all edges with lower weight, then find the lowest-cost path and test whether its cost is below the lower bound; that tells you whether the weight was too high or too low. Repeat until binary search converges.