patternMinor
Algorithm to find a simple path with maximum weight less than a constant in DAG
Viewed 0 times
pathsimplemaximumconstantwiththanweightalgorithmlessfind
Problem
Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should not exceed a given constant $K$.
Perhaps my question is elementary but I cannot find any solution. Indeed, it is well known that finding a simple path with maximum weight in $G$ is polynomial, but by adding the fact that this total weight should not exceed a given constant $K$, will the problem remain polynomial? because we need to keep at each node the set of path lengths that can be reached by the next vertices.
Perhaps my question is elementary but I cannot find any solution. Indeed, it is well known that finding a simple path with maximum weight in $G$ is polynomial, but by adding the fact that this total weight should not exceed a given constant $K$, will the problem remain polynomial? because we need to keep at each node the set of path lengths that can be reached by the next vertices.
Solution
Since there is no negative weight, you only need to keep at each node the set of path lengths no more than $K$. Because $K$ is a constant, you only keep a constant number of path lengths at each node. Hence, the algorithm remains polynomial-time.
Context
StackExchange Computer Science Q#114722, answer score: 2
Revisions (0)
No revisions yet.