# 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?

• How much have you tried finding cases when this problem might be NP-hard? Dec 24, 2018 at 21:19
• Why would you consider paths that enter a node twice? You will not gain any extra benefit. Dec 24, 2018 at 21:22
• @HendrikJan Imagine a path with only one entrance/exit with a big "fuel tank" at the end. Then the nodes alone the way will need to be entered twice (once on entrance, once on exit) Dec 24, 2018 at 21:28
• @BlueRaja-DannyPflughoeft Of course, a small detour to get a bonus. Thanks. Dec 24, 2018 at 21:45
• @Apass.Jack I have not tried much at all. Partially because I have a more specialized case in mind where the fuel would be relatively scarce, and I expect a reduction would involve a lot of fuel cans lying around. I would consider an answer containing a reduction to be a valid answer and accept it. Dec 25, 2018 at 0:53