1
$\begingroup$

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a particle can take to go from a starting node $s$ to a final node $t$. Every weight represents the amount of energy the particle loses when traversing an edge, and the particle cannot traverse an edge if it doesn't have the energy to do so (assume that the energy cannot be negative). The function $L(u)$ represents the energy boost the particle receives after reaching node $u$. If $L(s) = E$, find the maximum energy the particle can have when reaching the final node $t$.

I'm stuck at this problem. First, I tried to solve the alternative problem in which $L(u) = 0$ for every $u \in V \setminus s$, and came up with a solution with the Bellman-Ford algorithm. However, I don't see how could I use this result for the original problem. Maybe with a dynamic programming approach?

Improve this question
$\endgroup$
6
  • $\begingroup$ Where did you encounter this task? What is the motivation? Please credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W. ♦
    Oct 11, 2021 at 4:29
  • 1
    $\begingroup$ We have a guide on how to approach dynamic programming tasks: cs.stackexchange.com/tags/dynamic-programming/info. I suggest applying the systematic approach there, then editing the question to show us what progress you've made and where specifically you got stuck. $\endgroup$
    – D.W. ♦
    Oct 11, 2021 at 4:30
  • $\begingroup$ Can the particle visit a vertex twice? If it can, it might have no answers, such as the following example: G = ({1, 2, 3}, {{12, 23}), where all edge weights are -1, L(1) = L(2) = L(3) = 100, s = 1, and t = 3. It can constantly switch between 1 and 2 and gain more energy. $\endgroup$
    – Radin Zahedi
    Oct 11, 2021 at 19:01
  • $\begingroup$ @RadinZahedi: No because there are no cycles in the graph. $\endgroup$
    – Rob32409
    Oct 11, 2021 at 22:41
  • $\begingroup$ @Rob32409 Therefore you mean that the walk it traverses should be a path? $\endgroup$
    – Radin Zahedi
    Oct 12, 2021 at 10:04

1 Answer 1

Reset to default
1
$\begingroup$

For each node $u$, let $p(u)$ be the maximum energy the particle can have when it reaches node $u$ from the starting node $s$, or $\infty$ if it cannot reach $u$.

Hint, there is an orderly way to determine $p(u)$ for all $u$, node by node, thanks to the fact that the graph is acyclic.

Here is a more-revealing hint.

A topological sort will be useful.

Improve this answer
$\endgroup$

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.