I'm looking for an algorithm to solve this problem.I have a region in which there are several areas identify by its id and x,y,z position. I've made a graph in which each vertex identifies one ot these areas (for a max of 200 vertex). From a start point S, I know the cost, specified in seconds and inserted in the arch (so only integer values), to reach each vertex from each other vertex (a complete graph). When I visit a vertex I get a reward (float valiues).My objective is to find a paths in a the graph that maximize the reward but I'm subject to a cost constraint on the paths. Indeed I have only limited minutes to complete the path (for example 600 seconds.)The graph is made as matrix adjacency matrix for the cost and reward (but if is useful I can change the representation).I can visit vertex more time but with one reward only!I think to find the optimum solution is a np-hard problem, but also an approximate solution is apprecciated :DThanksI'm trying study how to solve the problem with branch & bound...
Find a path in a complete graph with cost limit and max reward
algorithms;graphs