HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Algorithm to find a simple path with maximum weight less than a constant in DAG

Submitted by: @import:stackexchange-cs··
0
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.

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.