0
$\begingroup$

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

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Okay so with your algorithm we know that we want use more than k skips, but maybe we will use less right? So k isn't the minimum number of skips we are looking for. $\endgroup$
    – Hjm
    Mar 1 at 19:54
  • $\begingroup$ 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 $\endgroup$
    – Highheath
    Mar 1 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.