# Minimum number of skips needed for shortest path

In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $$\leq W$$. In our given graph there is no such path but we have the ability to skip as many edges as we like.

How can I create an algorithm that calculates the number of minimum skips needed to find a path from s to t with weight $$\leq W$$?

Thoughts: In general we can use Dijkstra's algorithm to find a shortest in the given graph.

If the number of skips available in the graph was given the solution would be solution

Well, the answer from Codeforces is still correct, you just need to find a suitable upper bound for how many layers you will need. An obvious upper bound would be the number of vertices, but a better estimate can be made by just running BFS in order to find the shortest unweighted path from $$s$$ to $$t$$; if there is a $$(s,t)$$-path consisting of $$k$$ edges, you would never need to skip more than $$k$$ edges. Then, you can for each layer $$\ell$$ from 0 to $$k$$ calculate the distance from $$s_0$$ to $$t_\ell$$ and stop when it dips under $$W$$.
And, one note: In the answer it is not stated that the weight 0 edges must be directed (from layer $$\ell$$ to layer $$\ell+1$$). This is necessary in order for the shortest path algorithm to not go up and down layers and thereby skipping more edges than is allowed.
• So, in this case $k$ is an upper bound on the minimum number of skips (it's not impossible that it's not possible to do better), and therefore also an upper bound on the size of the graph you build Mar 1 at 21:57