Directed cyclic graph with node rewards and arc costs
I think this problem is NP-Complete via reduction to Knapsack Problem

An instance of the Decision Problem involves: a  Graph g, time alloted, sum_reward, and two nodes s,t
: Is there path from s to t with sum of rewards>=sum_reward within the alloted time period?

Reduction

Add nodes $s,t$ and an edge $s-&gt;t$ with reward,weight =0.
For every item a=(value(a),weight(a))
create a node  $n_{a}$ and the following two edges:


$e_{a}= s-&gt;n_{a}$ with $reward(e_{a})=value(a)$ and $cost(e_{a})=weight(a)$
$e_{b}= n_{a}-&gt;s$ with both values zero


I just noticed that rewards are on nodes instead of edges. But  this does not change the reduction(just transfer reward from edge to node)

Now run the algo for input ($G',knapsack$ $size$,$sum$ $reward,s,t$)$

IFF proof

=> if knapsack is feasible, simply iterate over edges of nodes contained in the knapsack and finally hop from s to t. This will give the desired sum_reward

&lt;= More or less, the same idea.

I hope this helps you somehow :)

Since your data is kind of special, perhaps someone can provide  an exact algorithm instead of an approximation one. I cannot (yet :P)