Hello everybody!
Recently I have faced the following graph problem: Given a directed graph with nonnegative weights. There is a need to find a number of paths between two nodes which path's weights are less then specified number. Graph may contain cycles and path may contain cycles.
I have found the Yen's algorithm which can find K shortest paths and which may be adjusted to partially solve my problem (the algorithm finds loopless paths) and wondering now if there is an approach to solve the problem.
You can use simple DP where
r[v][k]= number of paths from v to end with weight <=kWell, that's only if the weights are small numbers? In general with weights like 10^9 this DP will be horrible.
It looks like author have forgotten to specify limits so it is not clear whether simple DP or simple DFS or something else was intended to be used...
There is no limits for a problem, but they may be set as soon as identified. How would you solve such problem with DFS?
Please give a link to the problem.
There is no link for a problem unfortunately
But where did you take it from?
This is an interview problem
In fact, your problem is NP-hard, because it's possible to reduce the longest path problem to it in polynomial time.