Resource Constrained Shortest Path program
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.
(5) For all , such that
(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.