# Find a path in directed acyclic weighted graph with constraints

Consider a directed graph with n nodes and m edges with weights that represent the distant between the nodes. There is a start node s and an end node e. We want to find the path from s to e that has the maximum number of nodes such that:

1) the total distance is less than some constant d
2) starting from s, each node in the path is closer than the previous
one to the node e. (as in, when you traverse the path you are getting
closer to your destination e in terms of the weights left in your path.)


We can assume that there is no cycles in the graph and no negative weights. Does an efficient algorithm already exist for this problem? Is there a name for this problem?

Thanks

-
If there are no negative weights, then your criterion (2) must always be satisfied, no? Or, more strictly, your criterion (2) is a requirement that all weights are positive, which simply means we can't use zero-weighted arcs, which is an easy constraint to implement. –  Dan S Mar 30 '13 at 23:15