Optimum path in a graph to maximize a value

Question

I'm trying to come up with a reasonable algorithm for this problem:

Let's say we have bunch of locations. We know the distances between each pair of locations. Each location also has a point. The goal is to maximize the sum of the points while travelling from a starting location to a destination location without exceeding a given amount of distance.

Here is a simple example: Starting location: C , Destination: B, Given amount of distance: 45

Solution: C-A-B route with 9 points

I'm just curious if there is some kind of dynamic algorithm for this type of problem. What the would be the best, or rather easiest approach for that problem?

Any help is greatly appreciated.

Edit: You are not allowed to visit the same location many times.

Answer 1

EDIT: Under the newly added restriction that every node can be visited only once, the problem is most definitely NP-hard via reduction to Hamilton path: For a general undirected, unweighted graph, set all edge weights to zero and every vertex weight to 1. Then the maximum reachable score is n iif there is a Hamilton path in the original graph.

So it might be a good idea to look into integer linear programming solvers for instance families that are not constructed specifically to be hard.

The solution below assumes that a vertex can be visited more than once and makes use of the fact that node weights are bounded by a constant.

---

Let p(x) be the point value for vertex x and w(x,y) be the distance weight of the edge {x,y} or w(x,y) = ∞ if x and y are not adjacent.

If we are allowed to visit a vertex multiple times and if we can assume that p(x) <= C for some constant C, we might get away with the following recurrence: Let f(x,y,P) be the minimum distance we need to get from x to y while collecting P points. We have

f(x,y,P) = ∞ for all P < 0

f(x,x,p(x)) = 0 for all x

f(x,y,P) = MIN(z, w(x, z) + f(z, y, P - p(x)))

We can compute f using dynamic programming. Now we just need to find the largest P such that

f(start, end, P) <= distance upper bound

This P is the solution.

The complexity of this algorithm with a naive implementation is O(n^4 * C). If the graph is sparse, we can get O(n^2 * m * C) by using adjacency lists for the MIN aggregation.