Okay, this is officially a 'Resource Constrained Shortest Path' problem. I have been given an algorithm in class , but I'm having a really difficult time understanding it. The algorithm is as follows:

Let

be a set of resources.

Let

be the set of nodes.

Let

be the set of nodes connected to node

.

Let

be the length of arc from

to

, assumed to be positive for all arcs.

Let

be the vector of resource consumption on the arc from

to

. It is not necessary that these are positive. Some arcs can replenish resources.

Let

be the set of labels for node

.

(

) - the data stored with a label:

the node,

the relevant path length,

the vector of resource levels,

a boolean flag. For label

these can be written as

.

Assume we start at the origin

with an initial vector of resources

. We can define a resource constrained shortest path algorithm as follows:

(1) Set

∅,

;

.

(2) Choose

the label such that

(3) If

then stop.

(4) Set

(5) For all

, such that

AddLabel

(6) Go to step 2

The process AddLabel removes and labels (including the label to be added itself) if the are dominated by some other label. By definition, label

dominates label

if and only if

One label dominating another implies a separate path to the same node that is shorter (or at least no longer) and consumes less (or at least no more) of every resource. In the case of no resource this algorithm reduces to a shortest path algorithm.

What I have to do is write down a general purpose formulation (recursion or algorithm) for calculating the cheapest way from Townsville to Villageville, using the above algorithm, and find the shortest path from each node to Villageville. How can the this information (shortest path to destination from each node) be used to find a lower bound on the cost of completing any partial journey using the algorithm used to find the cheapest way from Townsville to Villageville.

I am also unsure what is meant by the lower bound.