highest weighted path for multiple destinations

Question

I have a directed cyclic weighted graph. I want to find a path with the highest some of weights, in length of X vertices, and I don't care what is the destination. I only want to find the highest cost.

Answer 1

This can be solved via dynamical-programming-like algorithm.

As you have only just a few hundreds of nodes and X is round 10. You can assign each node v an array Fv with size X, and Fv[i] represents the maximum cost from the source to the node v with length i.

Let s be the source. Set Fs[0] = 0, and all other Fs[i] = -infinity.

All other arrays are initialized as -infinity array.

Now,

for each node v, do the following update:

Fv[i] = max{Fv[i], Fw[i-1] + cost(w, v) | where w is neighbor of v}

repeat above updates for at least X times, and then check Fv[X] for all v to get the maximum possible value you want.

You can use some extra information to retrieve the path, which should be very easy to do.

Above algorithm is a special case of Bellman-Ford Algorithm