Dynamic programming can be used to find the minimum possible weight of the longest arc in a path between nodes A and B on a given graph

But for some practical purposes, I thought finding the minimum weighted path between nodes A and B (in a graph) given weight constraint[inequality] for the weight of an individual arc would be more useful, how can this be done and what is the name of this problem?

For example[clarification]: suppose I presented a network G, and labelled nodes A and B. I tell you to find the path of minimum weight between them, given that the length of all the arcs in this path must be less than n. What is this problem called and what is its solution?

  • $\begingroup$ Um i think you just remove all the arcs with weight greater than n, and then just compute floyd’s or dijkstra’s. .. is this correct . $\endgroup$
    – Hisham
    Apr 12, 2021 at 1:40


You must log in to answer this question.

Browse other questions tagged .