Shortest path with nodes containing collectibles of negative cost Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible fuel tanks). A path from A to B is a series of contiguous edges starting at A and finishing at B. The net cost of a path is the sum of the weights of edges (including multiplicity) on the path minus the sum of the benefits of the distinct nodes (ignoring multiplicity) on the path.

In principle paths are permitted to visit a node more than once, but the node's benefit is only ever collected once (i.e. you can't pick up the same fuel can twice).

Is there an efficient algorithm to find a minimum cost path from A to B in this situation? What if you're promised that the input contains no paths from A to B with net negative cost? What if you're happy with heuristics that perform well when nodes containing 'fuel' are scarce?
This is NP-Complete, by reduction from Traveling Salesman Problem (TSP).

Take any TSP.  Give every city an extremely large "negative-benefit," and set the origin city as both the start and finish.  Now running a solver for your problem will give the solution to the TSP.



I'm not sure of any "efficient heuristics", but if you remove the condition that nodes are allowed to be visited twice, the problem becomes much easier.  If you subtract every nodes' "negative benefit" from all its incoming edges, it becomes a normal shortest path problem.